In all of my KMZ files, I couldn't find a real good example of an image that went to 1 megapixel with one side not being 1024 pixels. This was the best I can find - the image is 700 * 1106, which is only 774,200 pixels. But it definitely proves that you are not constrained by 1024 pixels in either dimension of the image. I usually am just lazy and resize the images I am working with so that the long side of the image is 1024 pixels - then I know I am within the Garmin 1 megapixel limit.
http://www.gpsfiledepot.com/maps/view/629/So, yes, you can do any combination of pixel dimensions as long as the overall pixels are less than 1,048,576 pixels (which is 1 megapixel, 1024^2). So your example of 666 * 1500 would work, but you are leaving some pixels on the table - you could do 699 * 1500 and it would also work.
I use mapc2mapc for producing tiled KMZ maps.
Instead of restating it here, see also my discussion on the resolution of tiles for KMZ maps:
http://forums.groundspeak.com/GC/index.php?showtopic=307548Dave