My question is what do you want this robot to be? Something smart that can control itself, with a remote to change it's behavior, or do you want it to be always remote controlled (like a remote control car)?

In theory, if its option 2, you don't need an arduino for the movement, pan/tilt, or the remote control. The arduino is only really needed for the stepper motor control you mention. You could easily take an input from a remote control receiver to instruct the arduino and therefore the steppers. Look at remote control plane tutorials for basic analogue servo control - the pan tilt module is two of these - very simple. This is a good tutorial from sparkfun - but look at the 'Traditional RC Application' photo - that is how simple the setup is (although it is missing a battery!). I'd then use essentially the same setup to a brushless speed controller and brushless motor for the movement.

Regards Arduino programming, the skills are the same whichever size you get. Start with a nano and try to get an LED blinking (there are lots of tutorials online). Get a cheap clone of the arduino though to save your budget for the main event - they work exactly the same. £3 on eBay should do you.