My album sizes are 2000x2000, all my music use those dimensions.
Also, I'm not implying necessarily that the resizing aspect of it is what takes a long time (It could be loading the art into stream, parsing it, etc), All I'm saying is having this pre-resized in the database will guarantee performance for music with larger album arts that are anyways way above the resolution of the iPod screen.