The common, D&D 3.5 fighter is a war machine, it is build to fight (effectively or not is another thing). But when it comes to out of combat situations, it's better built in technique to handle things is intimidating others.
So, aside from house-ruling more class skills and/or skill points, is there a class that has a good to great fighting potential, and can be useful in out of combat situations?
Depending on what supplements you want to consult there are quite some alternatives for a "fighting man" that have some more utility in and out of combat.
Generally speaking, the classes from the Book of Nine Swords - especially the Warblade! - are generally better and more interesting than the vanilla fighter. They easily bully the fighter into a corner and steal his lunch money without breaking a sweat. Also, they way the maneuvers work allows some flexibility to use them outside of combat as well.
If you want a more specialized approach, there are several classes that are better than the fighter in some specific area (especially skills or utility) but not as general and adaptable (e.g. often you're pretty much set on your fighting style). You have:
Further, there is the "Thug" class variant from UA that trades some weapon and armor proficiencies and the level 1 bonus feat for a much better skill list and more skill points.
Upon further deliberation, you're asking the wrong question.
3.5 is (or at least tries to be) simulationist. Therefore, most anything you can imagine your character can attempt. While part of this is certainly mechanical, a question of out-of-combat utility boils down to imagination: can you envision and leverage your environment and your character such that she can be useful?
Now, to be fair, some of your imaginings may require implementation by other people, but don't tell me that Roy lacks utility out of combat:
He, as leader of the party, creates the plans, marshals resources, and deals with the rest of the team. He's got fantastic out-of-combat utility, despite being "only" a fighter.
While basically every class is "better" than a fighter (save maybe a barbarian) at out-of-combat utility, a fighter played with sufficient backstory and imagination will beat all of them if they are played purely mechanically.
Creativity and utility in 3.5 comes from understanding how to manipulate the environment, not simply the numbers on your sheet.
Setting aside Tier 1 classes that can trivially pretend to be fighters (Druid comes to mind), you have three different and flavorful options.
Psychic Warrior, (Any from the tome of battle, but Swordsage tends to have the most flavour/skills), The Totemist (Incarnum), and the Factotum. Note that all of these classes (save the incarnum ones that aren't rated) are Tier 3, while fighters are tier... 5.
The psychic warrior does not need to invest all of their powers known into pure-combat powers, and consequently gains non-trivial utility choices that directly benefit out-of-combat situations. I've played a half-giant Psychic Warrior "named Gar" who had earth power and had tremendous fun out of combat with him due to his libertarian propensities. (He was quite prepared to discuss, calmly and quietly, why the guards wanted to confiscate his 20' deep crystal spear. Really weirded the GM out with that one). The earth power feat allowed for a remarkably nuanced "sonar ping" that came in handy when scouting. Quite a lot of fun, and the base model allowed for huge amounts of characterization and imaginative solutions to problems.
The Swordsage with a focus on dex/wis and 6+ skill points makes him excellent on the battlefield and excellent as a scout. While I've never played one, the swordsage is my choice if I ever have to play a fightery type and psionics are barred. Because the disciplines can key off skills, the focus of the class supports far more nuanced and effective skill use.
The Totemist ... as the guide says is a build-your-own monster. There are plenty of "non-combat" abilities that a totemist can get that (barring being talky) provides plenty of non-combat options.
The Factotum is a literal omni-skill, having every single skill as their class skill. With inspiration points (and font of inspiration taken 3 or 4 times) they can put up a remarkable simulacra of being a fighter for 3-4 rounds before they call it a bad hair day and go find a mirror somewhere. Outside of that, no other class even approximates their skills. Since they have ijiatsu focus as a class skill (as well as the dreaded craft:basketweaving), and can add their int to... basically everything (attacks, damage, basketweaving...) one way or another, this is the class chosen for maximum out-of-combat utility while probably being more effective than a bog-standard fighter. I'm playing one in a midnight game and enjoying it. The obscene hide checks make "normal" combats slightly redundant, however.
Using only core 3.5, the cleric, monk, paladin, ranger, and rogue all make for great "fighters" with more utility than the core fighter.
The combination of special abilities, better saves, and spells or spell-like abilities allow each class to manage well in this role. Note that only Paladin's and Clerics can use medium/heavy armor, and only Ranger's and Paladin's have a full Base Attack Bonus.
The exact usefulness varies depending on the character's level. While a lvl 1 fighter may easily beat a lvl 1 monk, the monk quickly outpaces the fighter with special abilities, and will likely destroy any fighter at lvl 20.
Any of these classes are capable of dishing out damage equal to or greater than a fighter, but only the Paladin and Cleric can take the same amount of damage due to comparable HP and armor proficiency.
It's worth considering a multi-class fighter if you really want utility. Starting with 1 level of Rogue provides 32 skill points vs a Fighter's 8 (and gives trapfinding).
P.S. A Druid with wild-shape is the best "fighter" around.
Don't underestimate the usefulness of the craft skill, either. I do agree that fighters get one-sided, same as the base sorceror does in my opinion (no diplomacy, really?). Also, I support the above answers mentioning more emphasis on roleplay and less on mechanics. An interesting story is worth more to me than many skill points or noncombat abilities, both as a player and as a DM. Skill points tell me about what they want their player to do, but character-created story and roleplay tells me about where they want their character to go.
It depends on how much you want to refer to 'additional' 3.5 content.... and also, define a 'fighting class'?
From 'Complete Adventurer' you have the ninja and scout classes, plus PrC's based on those styles. Both are very combat-capable, but they're better at observing without being seen.... and taking down sentries without being seen.
From the 'Miniatures Handbook', you have the Marshal and Healer - whilst both can fight, they're better at either motivating or healing those who need it, at any part of a battle.
'Complete Warrior' also has the Samurai - very combat capable, but also trained in facing down opponents, and making combat end before it even begins.
