If you're just starting out, I'd recommend a hypercardioid condenser first. Mid-range shotgun mics (and cheaper) will give poor results indoors unless you're specifically in an acoustically dead space, which limits their usability. A hyper will let you do dialogue, SFX, foley, and more without such limitations. I bought a shotgun before a hyper, and in hindsight I really should have done it the other way 'round.
The all-in-one field recorder option is also a fine approach for just starting out. The Zoom H4n and the Sony PCM-D50 are supremely versatile, and have important differences between the two, and you'll find most recordists have invested in one or both. There are yet-cheaper options (Zoom H1, Sony PCM-M10), but you'll trade off noise floor and features.
In my opinion, Rode has the best signal:noise ratio for the money on the market today, period. They're not the most transparent, or the most rugged, or the "best" (whatever that might mean to you), but they're a great value. The Oktavas are great for medium-to-loud sound sources, but have a pretty high level of self-noise for quiet foley. Know these limitations, shore them up with what you want to record in terms of subject matter, and make your choice accordingly.
If you go with buying mics, please don't forget that your budget must also include a pistol grip, shockmount, and windscreen, as well as any supports you might want like a boompole or stands. You can't record anything meaningful by holding a condenser mic by hand (unless it's an omni, and/or made by a firm like Earthworks). :-)