Do not recommend the Improved Unarmed Strike tree. Not very useful overall. Power attack tree and Combat Expertise tree better.
I have seen a fighter use Improved Grapple to good effect vs. a Hag. Situational, but useful.
Dwarf is a good solid choice. Humans get you feats faster. Half-Orc is good if you don't multiclass (you get strength) but since you want a tricky fighter I wouldn't recommend it.
I don't think Cleave is a trap, especially at low levels. Great Cleave can be a trap, but Cleave gives you a bonus attack when you drop someone. That ain't bad, if you are not Whirlwind Attacking at the time. Improved Bull Rush is situational, but if you have enough feats, you can spend a few on situational maneuvers.
So, taking into account feats others don't like, and going with dwarf, here is a sample Dwarven Fighter. This is not the uber-power build (that would be cleric, druid or wizard) but still pretty fun and maneuvery, while focusing on just being good with your weapon at high levels:
Dwarf Fighter
1 Combat Expertise
1F Improved Trip (note you should get a weapon that you can trip with)
2F Improved Disarm (some weapons give you a bonus to disarms)
3 Dodge
4F Mobility (gain 4 AC while setting your rogue buddy up for the flank)
6 Spring Attack (this one requires you to wear medium or light or no armor to work, but it is also a prerequisite for Whirlwind Attack even if you never Spring Attack)
6F Whirlwind Attack (good when you are surrounded by a mob of lesser beings)
8F Power Attack (helps vs. high DR creatures if you don't have the right DR-beater)
9 Improved Bull Rush
10F Exotic Weapon Proficiency: Spiked Chain
12 Iron Will
12F Quickdraw (this is good for throwing weapons like Javelins)
14F Combat Reflexes (this is fun with reach weapons)
15 Weapon Focus (Spiked Chain)
16F Weapon Specialization
18 Greater Weapon Focus
18F Greater Weapon Specialization
20 Improved Critical (Spiked Chain)
Other feats that I like: Cleave, Improved Unarmed Strike, Deflect Arrows, Improved Grapple, Great Fortitude. If you like all the above feats and want one more from this list, go Human instead of Dwarf.
Leadership can be fun too, but it depends on the campaign and on your DM.
Another option is to give yourself some aptitude with ranged weapons too: the feats Point Blank Shot, Precise Shot, Far Shot, Rapid Shot and Shot on the Run could replace the last 5 feats from levels 15-20. Then if you can't reach your foe and he won't come to you, you can still have some fun.
[Edit: If you do multi-class with rogue, then in addition to the Tumble skill I would recommend the Bluff skill along with the Improved Feint feat - feinting basically can make your opponent lose their dex bonus to AC, making them easier to hit next time and also allowing for sneak attack damage even if you are not flanking at the time].
Maybe we should look at this another way. Look at the section in the book on combat and after it talks about attacks, damage, healing, etc., it gets into special combat maneuvers. See if there are any in particular that strike you as something you want your character to be able to do, and do well. If so, there are probably feats that will help you. If not, then don't worry about buying feats for it. That can determine how many levels of fighter would be good for you.