Well, when you say RTS player and mention Red Alert and Starcraft, keep in mind the Total War games are different beasts from those. Even just the real time battle parts play significantly differently than other RTS games.
But as for your question, if the Medieval you're mentioning is Medieval 1, then go for Rome. If it's Medieval 2, then go for Medieval 2 if you don't prefer the Roman era. Medieval 2 has a bit more unit variety, slightly nicer graphics, slightly better diplomacy, and the religion angle is pretty fun if you're playing a Catholic faction. It's definitely not less on armies, you're just mostly discouraged from attacking other Catholic factions by the pope, but there are ways around it.
Also, f you don't have any bandwidth limitations and have a good download speed, you can buy Rome Total War gold (Rome with both expansions) for $10 off of Steam. Might be the best option since it's easily found and cheap. Then if you enjoy that you can pick up the others.