Do you have a style preference?
I think many people prefer Brut, and it seems to be what many Champagne houses produce the most of.
There are too many good Champagnes and sparkling wines under $500 for me to list. (And while I have many favorite wines, I declare Champagne my all-time favorite. Someone recently asked me if I could only drink one wine for the rest of my life, what would it be, and my answer was pretty quickly Champagne. I just can’t get enough of it.)
I’m not experienced enough to suggest a vintage for any, but most Champagnes are non-vintage anyway (with typically only the truly exceptional harvests declaring vintage, such as Salon.) I can at least give you some of the bigger Champagne house names and you can check them out depending on what style you prefer. Alas, I’m also not in a position to afford any of the truly great Champagnes for anything other than very special occasions, so my experience is limited with them as well.
Some of the better ones I know of are Krug, Gosset, Bollinger, and Laurent-Perrier, which you already know. (Personally, I say go for the Salon and report back immediately.)
For Ca. Sparklers I love Iron Horse Vineyards (Wedding Cuvee), Roederer Estates (Brut Rose), and J Vineyards (Brut.)
You might want to try the sparklers of other countries as well, like Sekt (Germany), Cava (Spain), or Prosecco (Italy - which is made using the charmat method Twoflower warned you about), or stay in France but look outside of Champagne (look for Cremants, like Cremant d’Alsace, Alsace is another French region known for producing good sparkling wines.)
If you’re near SF or NYC, I’d suggest a stop in The Bubble Lounge, where you can taste many different wines before deciding what to buy.