These two games are were the Total War franchise has shined the most. Shogun 2 was a great addition to the series, but it is still plagued with many problems simply by being on the Warscape Engine. Before I go into the differences, I want to point out that these 2 games are extremely similar, not clearly destroying the other in a certain category. One isn't the clear victor, though, I believe, in the end, one is better than the other. That out of the way, let's begin with the campaign portion.
Campaign AI: People seem to be split on this on. Ignoring the extremists, people still say there is a difference. Some say Rome's was slightly better, others, Medieval's. To me, they both perform fairly similar. If you're weak, the AI will break alliances and invade you. The AI is pretty much always aloof at best, keep a varying amount of troops in its city for arbitrary reasons, and field massive field armies, but refuse to keep multiple stacks together (unless its the Mongols). I'm fairly convinced the differences in AI people see between these two games are at random. Sometimes the CAI is entertaining and challenging, other times it will decide that the best action for the Moors in MTW2 is to sail over half its army to England to capture one city. Basically, your results may vary
City and Town management: Medieval pretty clearly wins here. Rome's basically came down to making sure squalor wasn't to overburdening your populace, and then slaughtering the populace when you failed to keep squalor form overburdening your populace. In Medieval, General's have an additional stat that affects the populace; there are decisions of whether the build a castle for better troops or town for more stable income; there's a larger variety in buildings, there's a larger incentive to special some settlements in certain areas, and more. Rome's wasn't horrible, but Medieval 2 definitely was superior in this facet.
Troop Recruitment and Management: Medieval 2, easily. Armies function the same way, but Medieval 2 has a much better recruitment system. In Rome, once you built a higher tier unit, there was little reason to build the lower tier one. In Medieval 2, troops has a cooldown timer, some as high as 10 turns before more could be recruited. This made it so lower-tier troops are still ubiquitous, even in the late game, and there was a much higher priority on keeping your elite units alive.
Campaign Progression: In Rome, campaigns are can consist of establishing a dominate force in the early game. Mid-game consists of combating the neighboring powerful states and remnants of smaller fractions while putting down the 20th squalor rebellion. Late-game consists of hitting Esc and clicking Quit game, then starting a new campaign, since you're an unstoppable force at that point. The only major change to the campaign is when the new Roman legionaries are introduced, and (if playing as Rome) the inner war between the Roman fractions after you refuse to kill your fraction leader again. Medieval 2 doesn't have that problem, well at least not to the same degree. Early game is about the same, but mid and late game have exciting additions. Instead of legionaries, and entirely new unit is introduced, gunpowder units. Instead of steamrolling neighboring fractions, you'll be worried about yourself getting steamrolled by the impeding Mongol invasion. Defeated the Mongols? Well, now face the Timurids (Monghols on steriods). There's just more to keep things interesting.
The power you beckon to, the Pope vs the Senate: This isn't much of a competition. The Senate gives you missions that follow no discernible logic, that you will completely ignore, making the Senate hate you. You'll be too busy expanding your own empire the way you want to, making the people love you; this will allow you to take Rome without making enemies with the entire world like the Senate keeps ordering you too). The Senate aspect is enjoyable, and the assessments and orders they give provide context and atmosphere for the world. but the Senate gives atrocious missions. In Medieval. the Senate is replaced with The Council of Nobles, whose missions are completely optional. Now we have the Pope. The Pope very much is a fun game gameplay mechanic. If you get on his bad side, he'll prevent you from attacking other Christian nations, or even excommunicate you and open you up to all of Christendom declaring war on your heretic ass. Get on his good side, and he'll conveniently make conquering the other European factions easier. The Papacy's mission were never as demanding, with most just demanding the player to recruit a priest for 200 florins, then rewarding you with 500 florins. The inquisitors were also a nice touch, as they forced the player to make sure your nearby family members were pious enough for the Pope.
Miscellaneous: Medieval 2 adds a few things that Rome doesn't have. A chivalry and dread dynamic based on your deeds, prisoners, more voices, crusades and jihads, and smaller things that just add a bit more to the game
So the campaign, in my opinion, is better in Medieval 2. But what about the main reason we play Total War, the battles?
The Battle AI: Same with the campaign AI. Both can put up decent fights, or run straight into your pikes. Results may very. I have noticed Medieval 2 makes it's units runs back and forth indecisively less than Rome, yet they also don't seem to mind been barraged by arrows as much as Rome's AI. The AI in both games is extremely similar, though I have noticed the path finding in Medieval's is a bit better, so having 1 soldier getting stuck on some terrain, thus glitching out an entire unit, is less likely to happen in Medieval 2.
Battles, how they play and look: Rome's battles quicker. Soldiers respond to orders faster, and fights end quicker. It's about holding your formation, but all rushing units to the correct position quickly as possible. The formation that collapses is usually going to lose. Medieval 2 slows things down. Soldiers are more sluggish in response time, so more emphasize is placed upon correct positioning. Medieval 2 focuses more on setting-up the effective charge and flank, which should seem obvious since cavalry play a larger role. Fights last longer and soldiers move slower, and this was a wise decision, as this makes cavalry more crucial. Since they run so much faster, they are the troops used to charge infantry not in formation, and the units to behind a fight to attack the enemy from behind. Neither system is necessarily better, and I should point out that I made the differences seems larger than they actually are. Both work well with the units you are given. Watching a fight is a bit more entertains in Medieval 2, ought the increased amount and quality of the animations.
Faction Variety: Rome's factions played much different from each other. There are some factions that are just variations of others, but there is a diverse amount of play styles in the game. Rome, for example, relies on its infantry. Spamming cav as Rome would get you laughed at in a MP battle. Parthia, on the other hand, plays completely different. They are more about setting up that cataphract charge above all else. Even barbarians play differently, with certain factions focusing on skirmishing, some infantry, some balanced, and more. There's a lot of variety. Medieval 2's factions separate into 3 categories. Those who focus on horse archers, those focus on cav, and Scotland. All the Christian factions are just variations of each other. Some will be slightly better at archery but weaker at melee, some have better cav but worse archers, ect... This applies to many of the Muslim and Eastern factions as well. Horse archers make a faction play differently, but they are about the only different kind of play style. Then there's Scotland; the best strategy being returning to the main menu and selecting a new faction, because they are basically a European faction without any decent cav, aka screwed. Many prefer Rome for this reason alone, the variety of play styles.
Unit detail: Something that does make surprisingly large difference is difference between how the units look. In Rome, all your units of a certain type look that same. In Medieval 2, many have different helmets, armor, and faces. They armor level they are at will even affect the armor they're wearing. It's a small detail that makes watching battles more interesting.
Other points:
Performance: Though a high fps isn't crucial for these games, it does hinder the experience ever so slightly if the frame rate drops too much. Rome, sadly, only uses one CPU core. This is why Medieval 2, despite looking much better, runs so considerably better. Situations that dip to 20fps in Rome may still run at 60fps in Medieval 2.
Mods: Varies, but there are more massive mods out there for Medieval 2, probably ought to the additional features. Both games have some quality mods that enhance the vanilla experience, but there's nothing quite like the Third Age mod for Medieval 2 for Rome.
Expansions: Barbarian Invasion adds a completely new setting. It's interesting, and arguably better than Rome vanilla. Medieval 2 Kingdoms adds a bunch of new unique factions and play styles, especially in the American campaign (even if the new Apaches, Aztecs, and the like blow); Kingdoms also had the benefit of fixing the 2-handed weapon bug, which would make 2-hand units much less efficient at combat as they'd take longer to complete their attack animations. They both work fine. They are both wonderful additions. It's a tie, so long as you leave the horrible Alexander expansion for Rome out of the equation.
Please add to this. I know I've missed so much. Just remember, before you berate the other side's point and call a certain feature of their preferred game crap, Rome II at launch probably did that feature worse