Yo personalmente siempre utilizo un fondo con un degradado hecho en photoshop. Relleno una capa con el mismo color que el ela página y le aplico un degrado con otro color.
A veces lo hago con una imágen tan sola y otras repitiendo, repitiendo te aseguras que se verá en todas la resoluciones.
La verdad es que no se bien bien cual sería la más óptima...
Te pongo algunos ejemplos míos por si te sirven:
http://www.jmusicspain.com/images/bg.jpg http://shibuyadepako.iespana.es/image/bg.png http://pinkujisatsu.iespana.es/images/bg.jpg