SHARK, have you seen the little Power Classes booklets put out by Mongoose? If not, you might want to check them out. They only cost $2.99. Each is dedicated to giving the rules for one all-new base class, and one of them is called "Knight". Pretty cool class, if I do say so, myself. You may want to check it out, as it may suit your purposes (For one thing, you get a bonus feat every 5 levels).
As for the Paladin, I REALLY wish they had given them a Bonus Feat every 5 levels, but what're you gonna do? I don't think that would've been over-powering at all, but there it is. Of course, if you want to give other classes extra Feats, while still keeping the Fighter balanced, then how does this sound? Give the Fighter a Bonus Feat at every level, rather than at every even level. So a 10th-level Fighter will have 14 Feats, rather than 10. A 20th-level Fighter will have 27 Feats, rather than 18. Then adjust every other class, appropriately (Maybe not just with Bonus Feats, but with Talents, like those from D20 Modern). Just something I thought worth throwing out, there.