X Chris got to it before me. Algorithms are very useful for this, indeed. I am partial to the xBRZ scaling family of algorithms for up-sizing the bilateral filter
for general smoothing. Here are some nice examples here (part2)
. I guess the median filter is pretty useful too. For downsizing, X Chris's post may be my new favourite, we'll see after I implement it and compare.
IMO, most of the issues for aspect ratio involves the display hardware itself since not all screens are built the same. More specifically, the true pixel dimensions. Although if you are just using large squares rather than pixels to make the art 'feel' retro/pixelly/etc this isn't as much an issue. I would recommend making the art look good assuming the pixels are squares and leave the screen organization to the developer. If it is a wide screen make more of the background visible. I tend to think that is better than wasting nicer hardware after a threshold.