The Sandman, because it's just so fun. Just before I had a medic uber charge me outside the attacker's base, and I ran around with the Sandman melee, killed a Medic, Pyro and Engineer, and then when the uber charge ran out I stunned the Heavy as he was about to put holes in me and ran away, that was only possible with the Sandman. Plus, it's fun hitting people from 100 metres away and seeing them run around like "WTF?".
Oh, and as for hats. I've only played 40 hours and I've got a hat, and I got it ages ago, probably at around the 25/30 hour mark. I assume it's just luck?