Dude, get ImageReady, look at Loz avatar. I made that from a like 300x400 or something gif just by using the "Image Size" button on the edit menu of ImageReady, no errors except it's sorta fast, but that isn't because of the resizing.
I have never heard of ImageReady. Must be some weird, unpopular crap. Lol.
But I'd advise:
Paint.net (no relation to the Paint in Windows, btw)
The GIMP (very complex, kinda hard2install, but you can make high quality stuff with it)
And if you have the moneys, PhotoShop.
BTW, it's possible to use MS Paint to resize something... It's just kinda hard and not very user-friendly...