I know how you feel about always playing the Byzantines - I nearly always play the Romans in RTW. But if you can force yourself to try another faction, you may enjoy it.

I'd second the recommendation of the HRE. I find their strategic position fascinating - large empire, surrounded by hungry neighbours. I like turtling and this faction is the turtle most sharks want to eat...

As a Englishman, I am also drawn to my country's starting point. Being on an island, in the corner of the map, it has great strategic freedom - apart from having to contend with the French, you can do almost anything you want. A sort of anti-HRE, in that respect.

The most fun I ever had with MTW was taking a mid-game reign in an Almohad PBM campaign. The Almohads had half of Europe and a powerful AI Byzantium (with masses of heavy cavalry) had the other half. The clash was exhilarating.

Poland has a fun (and challenging) starting position. Very precarious but with a lot of fairly empty steppe you can conquer (just in time for the Mongols to arrive).

France has arguably the most fun early GA goals (the Krak de Chevaliers).

The Turks and Egypts have a rather different feel to the Catholics. And I love the Islamic battle music.