You did well choosing a small screen for the TV.
I'm afraid it's true that the Wii looks suboptimal on fixed-pixel displays, which all of them are these days.
All you can really do is look for a television with a quality scaler, or get an external scaler like the DVDO Edge. I've heard Samsung plasmas have a good scaler for dealing with 480p and 480i content, but I'm not certain because I've never had one.
I don't think it matters what resolution the output has to be scaled up to, but you should be safe choosing a lower resolution TV, because the 1080 definitely doesn't help in displaying 480p content at all.
If you're dissatisfied with the display even with a quality scaler, you have little choice but to hunt down a used CRT, or not play the Wii at all. TV manufacturers just don't care about Wii owners, unfortunately.