Cavalier.
Order of the Cockatrice gives Dazzling Display as a standard action.
Take COMBAT ADVICE (it's thematic).
Pump your CHA (and some WIS for saves) and you don't need to worry much about your physical stats when you're fighting from the back of a GRIFFON (preferably a FLYING GRIFFON).
No reason not to go with Mr Charisma's idea. Just a few notes - a feat or two building on dazzling display (perhaps disheartening display) could be reasonable, and he should have at least a few ranks in shipboard skills (profession (sailor) and knowledge (geography)) as well as social skills given his likely background.
Another option would be an Oath of the People’s Council Paladin. You trade out smite evil for some bardic performances. You also get Aura of Courage, and Aura of Resolve. These abilities seem more useful to a leader than dazzling display.
As a paladin he has good fortitude and will save and divine grace gives him CHA to all save. He is also immune to charm, disease and fear. Being immune to charm and fear is a definite advantage for a leader, and makes him very difficult to manipulate. The leader that goes down quickly is not that effective of a leader. So the paladin’s survivability is a huge advantage.
As a paladin he can also heal his troops after a fight. At 8th level his channel energy is only 4d6, but to low level troops that will be enough to make sure they are fully healed after a fight. Make sure that Fatigued is one of your mercies. This is going to mean that his troops can fight a lot longer than other troops.
The paladin’s spells are also going to be very useful for a leader. He gets lesser restoration as a 1st level spell. Some other useful 1st spells are comprehend language, detect charm, honeyed tongue. For second level spells eagle splendor, protection from evil communal, widen auras, and zone of truth. These are in addition to the normal combat focused spell a PC paladin normally uses.
Lastly a paladin is more likely to have a larger army and they will tend to me more loyal to him than a character that is always looking out for himself. The order of the cockatrice is very focused on the characters interests. The edicts of the order state the cavalier must always put his own interests above all others. I often give my NPC’s leadership in a situation like this. The followers from the feat are the followers that will always be loyal to the NPC even when in conflict with others in the government.
Re weapon, probably something not too big - as an admiral he'll be spending a lot of time in cramped shipboard rooms or around the rich and powerful, and the latter tend to ask you to leave carried weapons in the stables. Maybe a one-handed weapon which he can use two-handed like a standard longsword.