You will need stones as well as a knife, but fortunately both can be had for well under your budget.
For the knife, this Yoshi looks like a good deal:
http://yhst-27988581933240.stores.yahoo.net/yoshikane-wa-gyuto-240mm-sld-sanmai-uchi-blade-kn240.html
For stones, on a budget I think the Beston 500, King 1200 and the Arishayama 6k would fit well. From memory these can be bought for around $100-$150 for all of them. Check metalmaster-ww.com.
In my opinion, it's not a good idea to really splash out on your first good knife. You wont really be able to understand and appreciate it. The yoshi is very nice, but it won't break the bank, and you have other knives to look forward to in the future. If you are able to sharpen well and understand geometry, then I'm sure the Yoshi can be made to perform as well as much more expensive knives with thinning in the right places. For a start its best to build your skills rather than assuming the 'best' knives will give you the best results. Also no-one here will look down on the Yoshi, so don't think you're getting something second rate.
Of course there are many other knives and stone combinations which fit this pricing I have suggested, so look around, but remember that $$$ ≠ performance.
EDIT: Oh and don't forget something like an Atoma 140 for stone maintenance!