Yep, it's tough to inflict a name upon a party of PC's without it coming off sounding arrogant or just cheezy (and I'm not sure which is worse.)
First D&D game I played in lasted over 10 years and the party had already picked up a name before I joined - The Avengers. Don't really know where it came from or why, but I have long suspected it was a nod to the old TV show.
Second longest campaign I am proud to have been able to give the party their name - the Flashing Blades Adventuring Company. "Flashing Blades!" was a battle cry I used for my swashbuckler character and it just sort of got picked up by everyone on a general wave of engendered enthusiasm.
After that we TRIED real hard to give our PC groups a name but nothing seemed to work. One group sorta got named The Replacements because the cast of PC's had a high rate of turnover, but it was a meta-game thing. It was the players making fun of their own characters, not something the PC's themselves would have come up with and taken pride in and rallied around. It was a repeated problem in every campaign until...
I ran my first 3E campaign which lasted a couple of years. Sending the PC's through the WotC Adventure Path modules (or at least most of them) they went through Speaker in Dreams, which I set in the city of Arabel in the FR. They "saved the city" as per the module and were given medals that read, "Hero Of Arabel". They became "The Heroes of Arabel", or HOA for short (and pronounced "hoo-ah", in the Marine Corps fashion.)
I thereafter decided that whatever the name of future PC collectives would be, it would come much faster and sound much better if it's based on events in the game world, not "wishful thinking" by the players of the characters. If you see what I mean...