500 pixels wide and let the height turn out as it would by keeping the aspect ratio.
Just chucked it into Xara and it said "ooh that's a bit big, shall I reduce it to 500 pixels for you?" and so I said "yes"!
Dropped the filesize by a factor of 4 - 5 too, which is going to please anyone without broadband.