celestial mechanics - Two body orbit of equal masses

I know they will be orbiting about a common center of mass, i.e. the
barycenter. But, do the velocities have to be equal in magnitude and
opposite in direction (normal to R when R is their distance from each
other) for the orbit to be stable?

The orbital velocities do not have to be and in general are not equal in magnitude. What is equal is the angular velocity, that is the angular rate (e.g., in $rad/sec$) that two bodies will be orbiting their common barycenter. The orbital radius, $r$, orbital velocity, $v$, and angular velocity, $omega$, are related by the equation

$$omega = v/r$$

Note that these are all scalar quantities and $v$ can be thought of as the component of the velocity vector which is perpendicular to $r$. Since conservation of angular momentum implies that $omega$ remain constant for each body, individually, then we know that $v/r$ must also be constant which implies that bodies which orbit farther away from the barycenter must necessarily be orbiting faster and vice versa.

Now of course that simplifying explanation works for two bodies. Once you throw in more than two bodies, things become more complicated and the barycenter can move around, causing more complex motions.

I think, if the velocity of one mass were to vary with respect to the
other it would create a moving barycenter in which the two masses
would collide or throw on another out of the orbit

This is a subtly different question. If one of the two masses had a varying orbital velocity, that would imply it was gaining or losing energy by some mechanism. This can occur through things like tidal interactions as it does for our Earth and Moon. As stated above, the angular velocity must remain constant which implies that the body whose velocity is changing must also migrate towards or away from the barycenter, potentially resulting in a collision or escape. Since the Moon's orbital velocity is being sped up through tidal interactions, it is moving farther away as a result. Another example might be two black holes emitting gravitational waves as they orbit which propagates away energy and thus they orbital velocities, causing them to get closer together until they collide.