Although possible not a Federation Member, most Federation species could not serve on a Medusian ship, they couldn't directly interact with the crew.
Unless they had previously done a six-month tour on a Tellarite ship, in which case the inability to interact with aliens would be just what the doctor ordered.
But don't underestimate the effect of environment. Let me muddy the waters by suggesting two other things:
1) basic portrayals aside, it's EXTREMELY unlikely that all Federation races breathe the same atmosphere or are comfortable in the same gravitational/lighting conditions. Vulcans in particular are used to a thinner atmosphere with probably a lower oxygen partial pressure; it's evidently much easier for Vulcans to adapt to human atmospheres than the reverse. Likewise, frigid Andor probably has a much lower CO2 content in its atmosphere than Earth does; at room temperature, humans breathing Andorian gas mixtures would have a strong tendency to hyperventilate. And this assumes that all or even most Federation races breathe a similar range of oxygen/nitrogen mixtures; methane breathers would be out of luck, especially since their bodies would probably rely on ammonia instead of water. Gravity, also, can be a very important factor; a life form that evolved in less than one-sixth gee wouldn't even be able to WALK on in normal gravity and probably wouldn't survive there for any amount of time.
2) Home port. Warp drive may be fast, but it's not that convenient; Federation citizens don't commute between planets, so almost everyone still lives on the planet they were born on, which is USUALLY their own homeworld. Even if you could be comfortable on an Andorian ship, you'd have no reason to apply to the Andorian FLEET because you don't live anywhere near Andor and don't know anyone who does. The exceptions in Starfleet -- Spock, Worf, Data, etc -- all join Starfleet mainly because they've come to make their homes on Earth or in Earth-controlled colonies. Which would nicely explain why we never see the fleets of the other Federation members: with the singular exception of Vulcan, never really get to see other Federation WORLDS.