The bad thing about a $2000 budget is that a lot of the A-list games are well out of your price range. The good thing about a $2000 budget is you still have a ton of options.
I'd start with WPC games first. They are the highest quality machines from the era and have great software, sounds and personality. For $2000 or under, look at games like Demolition Man, The Getaway: High Speed II, World Cup Soccer, Fish Tales, Judge Dredd, No Fear, etc. They are all going to be of "player condition" quality, so expect faded cabinets and well-used/heavily routed examples.
Going from there, you've got a lot of options in the Data East lineup. Last Action Hero and Jurassic Park are good examples. Early SEGA titles fall in this category since they were basically transitioning from Data East: Baywatch, Frankenstein, Maverick, etc. All solid games and can be found for $2000 or less (Frank and Maverick are usually between $1400 and $1800). I'd personally avoid the tiny-DMD era DE games (Batman, Hook, TMNT, etc)--the rulesets on those typically aren't very good. You want a first game that's going to have some meat to it and provide a decent challenge. You also want it to last you a while, not something you are going to consistently see through to the end of in a day.
Moving downward, you've got the later SEGA games. They aren't the best games out there from either a quality or rules perspective, but they usually have a lot of ramps, are fast and the prices are low ($1800-ish for a lot of them). Starship Troopers, Goldeneye, X-Files, Independence Day, Lost World: JP, etc.
Some early Stern games can even be pretty cheap (under $2K). High Roller Casino, Striker Xtreme, Sharkey's Shootout, etc. I won't recommend the later two (Striker because it's weak, and Sharkey's because I haven't played it), but HRC is a cool game with a solid ruleset. I've seen it as low as $1200.
If you want bottom-of-the-barrel stuff, there are the Gottlieb DMD games. Street Fighter II, Super Mario Bros., Big Hurt, etc. I wouldn't really recommend any of these as a first pin--the flippers are goofy and the machines feel kind of clunky overall. Maybe try some later on if you get hooked, especially Stargate or Waterworld, but avoid this manufacturer for now, you have a lot of other choices.
Hope that helps!