In addition to legionaries, whose equipment and division varied a lot through time, the Roman army had auxiliaries, often foreign troops with their unique equipment. Cavalry, for example, consisted often of "barbarians" and formed a separate part of the army. In the later legions, cavalry played a more central role. Also, officers have been known to ride on horses or other mounts throughout history, so the player would still get to enjoy riding.
As to sea battles, they would be a bonus - not the main feature. The Roman tactic was basically to fight "land battles" on water, so it would not be difficult to simulate a boarding action between two galleys, for example.
But as I said, designing a new game is not topical. I'd like to see Mount&Blade released first. It has a lot of good potential - but it would fit a Roman setting very nicely! Or the Viking Age... Or a "Braveheart" scenario with William Wallace's war for independence (which has surely influenced M&B) where the player would be recruiting clans to fight the English... Or any one of the Crusades...
I do think that a historical setting would be nicer than a Fantastic one. Adventuring in the Highlands, for example, would be a lot more interesting than wandering in the outskirts of a place called Zendar. Also: this game has no magic! That's perfect when considering a historical scenario!
If you want more options, the late middle ages would provide even more variety in terms of interesting equipment. But I like the ~1000 A.D. setting I see in M&B.
The sequel should, of course, be Mount&Blade: Siege - taking warfare from raiding to capturing castles and perhaps even cities.
