There are no clear cut answers. This will take some 'touchy feely' balancing by the DM if you want to get this right. Campaign specific issues can make certain abilities ine game useless, while those same abilities in another game can be invaluable. If you want to get it right, you'll have to balance it yourself.
The key words are ECL. What mount would be powerful enough to have an effective character level equivalent of a 16th level character in that game.
It should be no more effective in melee combat than a 16th level character specialized in melee combat. If it is, you've made a bad choice.
If it can do more than fight in melee, the fighting ability needs to be weaker. The greater the quality and quantity of things it can do outside of melee combat, the lesser of a melee fighter it should be.
You've gotten a good number of suggestions from these boards. Give a few of them a try in mock situations and see which ones hold water ... and which ones seem to strong or too weak.
