I started with a 4x4x4 cube. with just resistors, leds, and an arduino. I would recommend doing what I did, start as simple as possible, then figure out ways to improve it. You will learn why something is a good or bad idea.
Soldering the cube is actually a bit more difficult than mike would lead you to believe (no mike, monkeys dont solder). You may want to look up some instructables.
A 4x4x4 cube can be controlled with nothing but the arduino (using 20 pins), and its about as big as you can get, without getting more complicated, so thats a good starting point. You will learn how to solder up a 3D object without using a PCB, which is challenging for most. You will also learn about multiplexing (a good time to learn abut charlieplexing too, but you may want to save charlieplexing for a different project.)
After you have mastered a simple cube, you can move on to learning how to control many inputs/outputs with a few control lines using electronic components for converting parallel data into serial data. Shift registers are a good start, there are also more sophisticated ways using LED drivers, which is where things get really complicated... so start with shift registers, then drivers.
I made an instructable to explain how to convert the 4x4x4 cube to use shift registers, it can be found here:
RGB is just 3 LEDs where you used to have 1 LED, but it really does complicate matters quite a bit. I started with a n 8 LED setup using ShiftPWM, its well documented and supported here, so its what I used to learn more about controlling RGB LEDs.
I am anxiously awaiting for some RGB LEDs to arrive, I have plans on making a 4x4x4 RGB charlieplexed cube that uses no other electronic components (64 RGB LEDs, Solder,Wires, Arduino ) If all goes well (which probably wont...) I may do an 8x8x8 charlie cube. Thats 512 LEDs, and over 2,000 solder joints!