Classes never let you take just “any feat,” or even “any feat you qualify for.” They always have some kind of restriction—whether it’s a specific feat, or something off of a small list, or any feat that matches certain characteristics or has a certain tag, there’s always something. For example, the Pathfinder fighter can choose any “Combat” feat they qualify for—that’s not any feat, but only those feats that are noted as “Combat” feats. The 3.5e fighter was much the same, though there wasn’t any “Combat” designation and you just had to see each feat’s Special entry. But no class just gets “any feat.”
But still, we can focus on the classes that have at least some options available.
Currently, this answer is, I believe, complete with respect to 3.5e. Variants and so on are almost-always restricted to core classes in 3.5e, which makes it easier to narrow things down (most of those are already represented on the list anyway).
Pathfinder is much harder, because of all the archetypes. That will take longer to find everything.
D&D 3.5e Classes with options
These D&D 3.5e base classes get a bonus feat at 1st, and that feat allows at least some choice in what feat that is.
Barbarian
With the city brawler variant from Dragon vol. 349, you get Improved Unarmed Strike and Two-Weapon Fighting (for unarmed strikes only) as bonus feats at 1st.
Also, several of the totem variants offer bonus feats at 1st, but you should never take those because they mean not taking the lion spiritual totem from Complete Champion, and that offers pounce.
Cleric
3.5e cleric is one of the best single-level dips in the game, because your two domains are so flexible. There are many, many domains that grant a bonus feat, so it’s easily two bonus feats in one level. And you can always trade a domain for the corresponding Devotion feat from Complete Champion, and those are some excellent feats. The cloistered cleric variant is even better, since it also gets Knowledge domain for free, which can be traded for Knowledge Devotion—guaranteed +1 to attack and damage, with a chance to roll for better numbers.
Also, turn undead is used to power a lot of useful feats, and orisons and 1st-level cleric spells are nothing to scoff at.
Fighter
Obvious, and mentioned in the question, but worth pointing out that the pugilist variant from Dragon vol. 310 gets Improved Unarmed Strike, Endurance, and another bonus feat, for a total of three bonus feats. Only the cleric can match that, and that depends on your choice of domains.
Note that there are tons and tons of variant fighters that get different options for feats.
Marshal
From Heroes of Battle, the marshal gets Skill Focus (Diplomacy) as a bonus feat at 1st. Usefully, maybe, it also allows you to take any other feat you qualify for if you already have Skill Focus (Diplomacy)—it’s extremely niche, but it could potentially be worth it to “delay” a feat, e.g. take Skill Focus (Diplomacy) at 3rd so you can take marshal at 4th to get a feat you qualify for at 4th but didn’t qualify for at 3rd.
I have literally never actually wound up using that trick, though.
Monk
Monks get Improved Unarmed Strike and one other bonus feat at 1st level—it’s almost like pugilist was referencing something ;). Originally the bonus feat had to be either Improved Grapple or Stunning Fist, but there are so many variants, alternatives, and supplemental features that your options are actually a great deal broader than that.
Psion
The psion gets a bonus psionic or metapsionic feat at 1st.
Psychic warrior
The psychic warrior gets a bonus fighter or psionic feat at 1st.
Rogue
This variant rogue gets fighter bonus feats instead of sneak attack.
Wizard
Wizards get Scribe Scroll as a bonus feat at 1st, and thanks to variants and alternatives, there are plenty of other options available—including any fighter bonus feat.
Wu Jen
From Complete Arcane, the wu jen gets a bonus metamagic feat at 1st.
D&D 3.5e Classes without options
The following D&D 3.5e base classes get some specific bonus feat at 1st—not requested, hence sorting them to the bottom of the list, but since I found them it seemed worth listing them.
Archivist
From Heroes of Horror, the archivist gets Scribe Scroll as a bonus feat at 1st.
Artificer
From Eberron Campaign Setting, the artificer gets Scribe Scroll as a bonus feat at 1st.
Battle Dancer
From Dragon Compendium, this awkward monk-like class gets Improved Unarmed Strike at 1st.
Dragonfire Adept
From Dragon Magic, the dragonfire adept gets Dragontouched as a bonus feat at 1st.
Druid
The variant druid gets Track as a bonus feat at 1st.
Ranger
Ranger gets Track at 1st. It’s pretty weak, but it’s a bonus feat. Unlike the monk, this one hasn’t been substantially expanded upon—Urban Tracking is the only other option I’m aware of.
Samurai
From Complete Warrior, the stunningly-bad samurai gets Exotic Weapon Proficiency (bastard sword) as a bonus feat at 1st.
Soulknife
The soulknife gets both Weapon Focus (mind blade) and Wild Talent as bonus feats at 1st.
Swashbuckler
From Complete Adventurer, the swashbuckler gets Weapon Finesse as a bonus feat at 1st.
Swordsage
From Tome of Battle, the unarmed adaptation mentioned at the end of its section gets monk-like unarmed strikes, which would include Improved Unarmed Strike at 1st.
Pathfinder
These base classes in Pathfinder offer bonus feats at 1st. (So far I have only gone through the core classes.)
Barbarian
Barbarians do not get any bonus feats at 1st by default. The following archetypes, however, do:
- Primal hunter gets Exceptional Pull as a bonus feat (ignoring pre-reqs) at 1st.
Bard
Bards do not get any bonus feats at 1st by default. The following archetypes, however, do:
- Arcane duelist gets Arcane Strike as a bonus feat at 1st level.
- Dervish of dawn gets Dervish Dance as a bonus feat at 1st level (mentioned in the question as an example of what isn’t interesting, but for completion’s sake).
- Geisha gets Scribe Scroll as a bonus feat at 1st.
- Juggler gets Deflect Arrows as a bonus feat at 1st.
- Lotus geisha gets Spell Focus (enchantment) as a bonus feat at 1st.
- Magician gets Improved Counterspell as a bonus feat at 1st.
- Mute musician gets Eschew Materials as a bonus feat at 1st.
- Phrenologist gets Psychic Sensitivity as a bonus feat at 1st.
- Studious librarian gets Scribe Scroll as a bonus feat at 1st.
Cleric
Clerics do not get any bonus feats at 1st by default. The following archetypes, however, do:
- Angelfire apostle gets Extra Channel as a bonus feat at 1st.
- Crusader gets your choice of Heavy Armor Proficiency, Improved Shield Bash, Martial Weapon Proficiency, Saving Shield, Shield Focus, Tower Shield Proficiency, or Weapon Focus (deity’s favored weapon) as a bonus feat at 1st level.
- Divine paragon gets Deific Obedience (ignoring pre-reqs) as a bonus feat at 1st.
- Undead lord gets Command Undead as a bonus feat at 1st.
Druid
Druids do not get any bonus feats at 1st by default. The following archetypes, however, do:
- Supernaturalist gets Psychic Sensitivity as a bonus feat at 1st.
- Feral child gets Improved Unarmed Strike as a bonus feat at 1st.
Fighter
Fighter, obviously, gets a bonus combat feat at 1st level.
Monk
Monk gets three bonus feats at 1st level, Improved Unarmed Strike, Stunning Fist, and one other feat chosen from a small list. The default list is Catch Off-Guard, Combat Reflexes, Deflect Arrows, Dodge, Improved Grapple, Scorpion Style, or Throw Anything, but archetypes may make other options available.
Paladin
Paladins do not get any bonus feats at 1st by default. The following archetypes, however, do:
- Divine hunter gets Precise Shot as a bonus feat at 1st.
- Enlightened paladin gets Improved Unarmed Strike as a bonus feat at 1st.
- Holy gun gets Amateur Gunslinger and Gunsmithing as bonus feats at 1st.
- Pearl seeker gets Psychic Sensitivity as a bonus feat at 1st.
- Virtuous bravo “counts as” having Weapon Finesse at 1st (and gets similar benefits but only with piercing weapons and takes any shield’s armor check penalty as a penalty against attacks).
- Tranquil guardian gets Touch of Serenity as a bonus feat (ignoring pre-reqs) at 1st.
Ranger
Ranger gets Track as a bonus feat at 1st. In addition, some archetypes get other feats:
- Divine marksman gets Bullseye Shot as a bonus feat (ignoring pre-reqs) at 1st.
- Divine tracker can get Improved Unarmed Strike as a bonus feat at 1st, if their deity favors unarmed strikes.
Rogue
Rogues do not get any bonus feats at 1st by default. The following archetypes, however, do:
- Consigliere gets Persuasive as a bonus feat at 1st.
- Makeshift scrapper gets Catch Off-Guard and Throw Anything as bonus feats at 1st.
- Pirate gets Sea Legs as a bonus feat at 1st.
- Scavenger gets Technologist as a bonus feat at 1st.
- Snare setter gets Learn Ranger Trap as a bonus feat at 1st.
Sorcerer
Sorcerer gets Eschew Materials as a bonus feat at 1st. The following archetypes offer other feats:
- False priest gets False Focus as a bonus feat at 1st instead of Eschew Materials.
- Sorcerer of sleep gets Sahir-Afiyun as a bonus feat at 1st instead of Eschew Materials.
- Tattooed sorcerer gets Mage’s Tattoo as a bonus feat at 1st instead of Eschew Materials. It’s implied that they can ignore the pre-req, too, since there is a rule for what happens if you don’t have it.
Wizard
Wizard gets Scribe Scroll as a bonus feat at 1st. Necromancers also gain their choice of Command Undead or Turn Undead as a bonus feat at 1st.
The following archetypes also get bonus feats at 1st:
- Arcane physician gets Brew Potion as a bonus feat at 1st instead of Scribe Scroll.
- Clocksmith gets Craft Construct as a bonus feat at 1st instead of Scribe Scroll.
- Fey caller gets Augment Summoning as a bonus feat at 1st instead of Scribe Scroll.
- Siege mage gets Siege Engineer as a bonus feat at 1st instead of Scribe Scroll.
- Spellslinger gets Exotic Weapon Proficiency (firearms) as a bonus feat at 1st.
- Spirit binder doesn’t get a bonus feat at 1st, but their familiar does, and that one actually is “any feat” that the familiar qualifies for.
- Undead master gets Command Undead as a bonus feat at 1st.
