Buy box-lots of 'darkroom stuff' off online auctions and be brutal with how much you are prepared to pay. I bought 2 box-lots for $50 and $40 respectively and had everything (except consumables) I needed to get going, plus a pile of spare stuff. (within the last 18 months). My 50mm lens is not one of the big names mentioned here, but i can make 12x16 enlargments from 35mm with it and the limiting factor is presently the quality of my negative capture/processing not the enlarger lens.
Don't overlook the cost of consumables and black-out materials in your budget. Builders paper is effective and cheap, but makes humidity/damp an issue (I just put up with it, and store my lens (with cameras) in a cupboard with some dessicant) Do your printing at night and black-out is much less critical.
Once you are printing you can think about what items you'd like to change/upgrade to make it easier/more fun. For example: I fairly quickly 'exchanged' my first enlarger for one with a filter drawer and longer column (cost of 'exchange' was another $60). But (to date) most of my improvement has come simply from learning.