Well... there's the Troglodyte (2 HD, +2 LA). Darkvision, +4 Con, and +6 Natural Armor are nice. On the other hand, the stench and the name are some turnoffs...
Hobgoblins provide +2 Dex, +2 Con, Darkvision, a bonus on Move Silently, and Fighter as their favored class, all for just +1 LA and no racial HD. Slap on the +3 template of your choice and you're ready to go.
A first level half-dragon hobgoblin fighter (ECL 5) would get +8 Strength, +2 Dex, +4 Con, +2 Int, and +2 Cha, +4 Natural Armor, the breath weapon, immunity to a type of energy, and natural weapons.
If you want to go with something amusing, you could try a half-fiend goblin. +2 Str, +6 Dex, +2 Con, +4 Int. Small size, so you get a bonus to your AC and attack rolls, but you use smaller weapons. But you pick up spell resistance, damage reduction/magic, resistance to acid, electricity, cold, and fire, darkvision, immunity to poison, even spell like abilities. Oh, and +1 Natural armor, you can fly, and you have natural, magic weapons. Plus, some of your abilities improve as you gain levels.
Slightly stranger would be a half-celestial goblin... +2 Str, +4 Dex, +4 Con, +2 Int, +4 Wis, +2 Cha. Darkvision, resistance to acid, electrcitiy, and cold, DR/magic, spell resistance, immunity to disease and a bonus against poison. Plus the natural armor, you can use daylight at will, a smite evil attack, spell like abilities... and you can fly.
Of course, those options have just your regular class level HD.