Well on the iPhone, you are pretty much flexible with the wallpaper size as how Repr0bate said, since you can zoom in and out of the picture and set it as your wallpaper
But still, the sharpest image will be at 320px x 480px (on iPhone, 3G and 3G S)
As you zoom in, the picture goes blur because you expend the pixel to cover up more area