Fighters are actually pretty good, you have a lot of options with them. If I had to take 5 levels of fighter to start out with and really wanted to multi-class out of it, I'd probably go with another martial class like Ranger, Barbarian, or Monk. Usually the best thing to do is a 1-2 level dip in something as you multi-class instead of 5 levels.
Are you constrained by your first 5 levels being the vanilla fighter or can you pick an archetype? Like you could get the Unarmed Fighter and transition into a monk or Brutal Pugilist pretty easily.
Due to story reasons for an upcoming campaign I am making a hobgoblin fighter starting at level 5. The characters first 5 levels must be in fighter, but the remaining levels are fair game. I really don't want to stay with fighter levels, so what are good multi-class options?
Honestly? I find that there aren't many (good) class combinations, and that dipping and such is rarely a good thing unless you want to sacrifice major concepts in the larger scheme of things. The Fighter Class, as far as I can tell, aren't a good class to Multi-Class with (that is, having it be your main class) I'm not going to go Wizard/Magus, and Dip a few levels into Fighter or Barbarian (for the extras), and then sacrifice something so much (Time Stop and Wail of the Banshee say hi) for something so little (+1 BAB, Rage/Bonus Combat Feat).
The best solution to having a variance/viability for your character (of which could actually allow you to multi-class, as ub3r_n3rd pointed out per example) is to utilize Archetypes to your advantage. I enjoy my Mobile Fighter a lot, and the benefits he gets for being the archetype he is, is beyond crazy, and makes him great for maneuvering combat (40 ft. movement speed, taking 10's and limited 20's per day to all Acrobatics checks, PLUS extra damage and hit bonuses for moving during combat, while maintaining the concept of Armor Training and Bonus Feats? Sign me up)!
I hope that helps, and it changes the spectrum of the Fighter Class (and your decision-making) to so many levels.
I'd probably go Ranger after fighter then. You get 6+ int mod skills per level as a ranger, they're good at stealth, they have full BAB just like a fighter and you can pick one of their cool archetypes as well if you really want to specialize in covert stuff, like the Battle Scout or Infiltrator. Rangers can do a lot more than just shoot a bow, they are pretty good at switch hitting using a sword/board or 2h sword too. You'd just have to pick your style and get the bonuses when you took your first level of ranger. I'd keep that in mind so that if you want to do well with fighting with a sword/shield or sword you pick the feats needed as a fighter than get some free combat style stuff from the ranger when you drop into it and then flesh it out. There are plenty of guides out there as well like the well respected Treantmonk's Ranger Guide.
skill heavy, including infiltration. You sure you can't build a Ranger?
Anyway, fighters synergise well with pretty much all martial classes. Barbarians, Rangers and Paladins included.
Fighter/Inquisitor is a good mix of combat/skills/spells, since many of the Inquisitor's class features use swift actions. And he has tons of skill ranks and class skills, including Bluff, Disguise, Stealth, Survival and Perception, which seems like will be very useful for a campaign like the one you described.
The Preacher archetype even allows you to trade Teamwork feats for a few cool abilites.
Ah, I see...
Barbarian, then? 4 skill ranks per level is decent, and you can up that to 6 if you're human (although I'd suggest getting onlt 5 and using the favored class bonus to superstion for a better will save during rage)
Or a Paladin? It's a very good class and they really benefit from extra feats. Although the allignment restriction and lack of skill points can be a deal-breaker. How about wizard for an Arcane Archer build?
Fighter 5 (Lore Warden) -> Wizard 2 -> Arc.Archer 2 -> Wizard 11?
What about a Pistolero Gunslinger? It could do wonders with 3 extra feats. But many players/groups/GM don't like the class and/or think it's OP.
Sounds like you have a few options as we presented them to you, have fun!
Personally, splash as little as needed. Two to three levels is it. The fighter's strength lies in BAB and bonus feats.
I'd lean to two levels as Inquisitor. Why? Shore up the the Will Save. Cunning Initiative, since a 12 or 14 into Wisdom does double duty for both Initiative and Will Save. Then all those extra skills to throw around. You don't really have to play it like an inquisitor. Just milk it for the goodness you get as a fighter with a few quirks.
Cleric would be next up. Shore up the Will Save yet again. I'd go three levels that route. A few more spells, spontaneous casting. Utility spells would be the order of the day.
Ranger, one level and done. Add a few skills, and enjoy a favored enemy. It takes two more levels to get anything major to buff the fighter side, hence the small splash.
Rogue, two levels. Stick with is for Rogue Talent (Canny Observer) and the huge spike in skills.
I'd disregard Magus. Not a boost in skills, spell selection is limited in the utility department. But it could be a gateway to arcane archer.
I'm gonna go out on a limb and say... Shadowdancer.
Bear with me: high skills, awesome at infiltration... Four levels (longer than most people recommend for a dip) gets you a few good things:
HiPS, darkvision, Evasion, Uncanny Dodge, a Rogue Talent (probably Fast Stealth), you can summon an incorporeal shadow that deals 1d6 STR damage, no save, and at fourth level you get 40 ft of shadow jump, which can add a lot to your movement options.
I am playing around with a glaive wielding ranger (with a spiked gauntlet, armor spikes, and a longsword as well) who spring attacks in and out with HiPS.
Anyway, it might be fun for you.
You could splash a level in sorcerer and go dragon disciple. You'll get some good boosts that will keep you on par (or better than) a regular fighter and you'll be able to nab some sorcerer spells. In a party of people that started out as 5th level fighters its not a bad way to grab those cantrips like detect magic and read magic.
Other options are bard and summoner. Summoners have a pretty rocking spell list and you can blow your summon monsters on traps or something and your dingus first level eidolon can be a skill monkey. As a bard you'll be able to inspire something and have some skill points also you'll be able to use wands of CLW which I find myself buying even at mid-high level (nothing like standing there for five minutes while a cram an entire wand in my ear). Your BAB is going to take a hit but you'll be all right, you'll have str boosts to make up for it and eventually you'll turn into a dragon which is cool (don't let nobody tell you otherwise).