The LED strips: some come with built-in controller chips, and can be controlled more directly. They of course cost more. Then the Arduino just tells the strip the brightness and colour it has to show, and the strip takes care of that. Makes the hardware part a lot easier.
Relay: consider using solid state relays. Unless you like the clicking noise.
I second the remote control idea. It's also a lot more flexible to be able to control your LED spots and the strip independently, instead of having to cycle through a number of programs.