I have won every "best of" series I've played online with other people. This ranges from people using Lucario, Marth, Toon Link, Snake (although he was pretty tough to handle at first because I knew nothing about his style), Metaknight, Ike, Pokemon Trainer (Squirtle was a hassle granted), and Sheik. There are been a couple of instances where the person was not that great of a player in which I won every match, but for the most part my matches online have been suprisingly competitive. However, I was able to adapt Falcon into whatever I needed him to be to combat my opponents' strategies and pull off a victory. The best thing I've noticed about Falcon is that he CAN kill at low percents, and he DOESN'T die at low percents. Also his edgeguarding is great because his uAir has good reach and pretty good knockback. His ground SideB is a little nerfed unfortunately (like how he doesn't go under Samus' missles anymore), but it still gets the job done. I'd MUCH rather have the Brawl version of his SideB than the Melee one though! The added aerial tweaks make it a GREAT move that's very versatile.
As for tiers, so far I'd say that they are not going to be very widespread at all. The best character and the worst character (which I believe is DK) are not leagues apart. Everyone is for the most part lumped together. I know it's early but right now that's how things are.
I'm not claiming to be the end-all know-it-all for Falcon, but I do know that he does not suck. And as long as I keep winning matches with him against every other character I'll keep that belief. Personally I think that everyone for the most part must suck with him in Brawl, because a lot of people I've played have told me that I'm the best Falcon they've seen by far and that everyone else is terrible with him. Now seriously I know I'm not the best with Falcon or even close to the best by any stretch, but obviously there are a LOT of Falcon users out there that are worse than me. Ever think that maybe all of those people are the reason why people think he's terrible? He is not the combo king he used to be, but he can still win matches if people know what they're doing with him.