That depends on the TV, but yes, you're usually better off starting with a sharpness of zero, because many TV's have noise reduction filters and whatnot that are not active when the sharpness is set at zero. At first, the picture may feel a bit "soft", but that's only because you're used to seeing an "oversharp" picture. Once you get used to it, you'll find that setting it any higher is just ugly to look at.
As for the 480P games looking pixelated, it is going to depend on the quality of the scaler in your TV. Some TV's can upscale a 480P picture to 720P (or higher) better than others. This is the main reason why I wished Nintendo had made 720p the default. The only way you're going to be able to fix this is by getting a new TV, or by getting an outboard video scaler that can send a native signal to your TV. Either option is fairly expensive. There are some home theater receivers that do a decent job of upscaling signals, which may be an alternative.