i started with premiere, then got avid mc3 which is by far the smoothest and most intuitive nle (for me), now i'm using premiere again, but missing the way avid trims and deals with bins & subclips and stuff.
avid is awsm, but the workflow (while presumably great for post houses) is kind of long winded for amvs
the way you trim is really nice. you can shuttle with jkl, then switch to trim mode and trim with jkl too, it's far better than wanking around with the mouse in premiere (why can't you shuttle in the trimmer in premiere??!). mc3 has an integrated compositor too, but it's like a tweaked version of boris and not even close to shake or ae.
fcp is really popular, integrates with shake (which is apparently on the way out, but really powerful node based compositor)
premiere is sometimes used on small productions, and presumably used a fair bit by freelancers, but is generally frowned upon

if you're using ae, ps, illustrator etc the integration is great.
vegas is great
for the money, but i hated using it - the retarded trimmer and speed limit when you scrub with the mouse made it unberable for me. i think vegas is a good enough all rounder, you can do a bit of everything with it, although you'll probably want ae or boris before long.