It's also worth remembering that in the basic source for Halflings -- that is, the Lord of the Rings -- the halflings are not killing machines. Two of their noteworthy blows in the story -- against the troll that struck down Beregond, and against the Witch-King of Angmar -- were delivered by surprise, using enchanted weapons. Another one -- Sam's against Shelob -- used another enchanted weapon and the spider's own mass to damage her. The only one-on-one, toe-to-toe kill was Sam's near Balin's tomb in Moria, where he killed an orc with "a sturdy thrust of his barrow-blade" -- and orcs, in the Lord of the Rings books, are pretty small. After all, the hobbits were able to pretend to be orcs by putting on their helmets.
So, unless a character's worth is going to be measured in how many bodies they can pile up, a small character is still viable if the story admits of something beyond "omgzzz kill kill killllll."
Furthermore, I believe this was the whole thing with the halfling's racial advantages with bows and roguery -- if you're small, it makes sense that you get overlooked by larger creatures, can fit into more places, etc. (rogue) and are better in combat if you keep your distance and fill the opponent with arrows (archery), the tactic used by the halflings in the Scouring of the Shire.
And Tolkien's halflings were a bit more than 3 feet, IIRC, though I would need to check on his addenda.
And finally, if you make halflings medium, what the heck is the point of playing one? Just say "I'm playing a human, and he's exceptionally short."