I would recommend looking at these two websites:
http://www.parallax.com/
http://www.crustcrawler.com/
Crust Crawler used to make some very cool crawler robots but it seems that they have since discontinued them. Still, they have some good servos, and their
Beginner Bioloid Kit might be right up your alley if you don't want a "rolling" robot. It can't realy make use of sensors or uneven terrain though...
Parallax is an excellent website that sells simple robots, and TONS of hobby-grade robotic components like sensor modules, control boards, etc. The
Boe Bot is a good little robot that comes in an educational kit, and supports many accessories like wireless interfaces, sensors galore, walker kits, gripper kits, etc etc. Another robot kit you might consider is the
Sumobot competition kit, which comes with two robots and a competition ring. It's still in your price range, and would allow you to try out different strategies and tactics and hone your programming skills.