Updated based on more experience and vids. As before, this is somewhat ordered within tiers, though I can't decide on a lot of the finer points of ordering:
High Tier:
Upper Mid Tier:
Lower Mid Tier:
Low Tier:
Thoughts on each tier:
High tier is the most difficult to order. I believe Fox and Ivy are clearly 1 and 2 - Fox is super fast and mobile and also packs huge power, and Ivy is to range what Fox is to speed with amazing recovery to boot. The rest of high tier could be in almost any order. In fact, that's how I choose the high tier cutoff, I originally had Shiek and MK there as well, but I feel they are clearly below those other characters, which probably means there's a tier separating them. All of the characters in the top tier perform very well in pretty much every matchup and have few to no significant weaknesses or bad matchups outside of their own tier.
The main thing separating upper mid tier from high tier is that matchups are more of a factor here. I have no doubt that the presence of Marth, Falco and MK in this tier will ruffle more than a few feathers, but all of them have issues with some of the new characters. In general, in Melee, if you did well against fast fallers, you were high tier, but in PM there's like 3 times more viable characters, so you need a lot more versatility to perform well against everyone, and Falco, Marth, and MK are not as versatile as Fox, Link and Kirby. Nothing else here should be a huge surprise, except maybe ROB, but I think he's very slept on. I also admit that I heavily underestimated Toon Link before, he's solid.
Lower mid consists of characters who generally have a couple holes in their game. Fox example, ZSS has huge range but huge startup on a lot of her moves, particularly her nearly useless grab. Wario is nicely mobile and has a good grab range, but he lacks disjoints and doesn't seem to get a lot of reward off his grabs. Charizard has big range on a few of his moves but isn't nearly as fast as Mewtwo and is massive combo bait. And so on. This tier is viable but you might need a secondary character for bad matchups. Incidentally, I moved Ness up to this tier, he's definitely not quite as bad as previously thought with his double jump cancels and solid throws, but he has issues with characters who are significantly fast or ranged (ie, most good characters).
Low tier generally consists of characters who are too one-dimensional to do well in a PM environment or have some other big issue. Probably the most controversial choice here is Samus, though I feel that she's kind of like a Ness but with inferior damage. Her keep-away is pretty slow and not all that powerful, and her close-range attacks don't seem to have quite enough oomph. I did move G&W up a bit, he's more versatile than a lot of these characters, he's just kind of janky in a bad way and most of his options feel a little weak. The Ice Climbers are really freaking bad now, they used to be characters who weren't great at neutral but hurt you so ludicrously bad if they ever got in that it didn't matter, but now their damage output has been completely butchered so they're just bad. They might even be worse than Puff, though Puff is really awful.