For anyone else who reads this:

dude was correct, all three are correct grammatically. I'm from the northeastern United States and, to me, there is a subtle difference in the tone of them.

1. I really must be going.

This is the most formal, the most polite, and the most friendly.

2. I really have to go now.

This one is more forceful because of the "now". I would not use this unless I had already said #1 and then I still didn't get to leave (for whatever reason) and need to emphasize that now was the time I had to leave, not soon, and I would emphasize the word "really", as in "I really have to go, now."

3. I really must go now.

This one doesn't sound very natural to me because "really must" just... sounds like it came from a 1950's movie. Instead, I would say "I really MUST go" or "I REALLY must get going". The tone of how this was said would change the meaning. It could very, very firm or even rude, but if said with a fun, flirty air it'd be a super dramatic way of expressing unwillingness to leave/regret at having to leave.