I had used MS paint for my first art. You can see it. And You can try GIMP, its small like 90 MB, and has powers like Adobe photoshop. Its powerful.

It's kind of hard to answer this with so little given details, but I'll give it a shot.

In general, no form of raster/bitmap graphics are designed for arbitrary scaling.  (If that's what you're after, vector graphics are by far the preferred choice.)  However, just because pixel art is raster graphics doesn't mean you *can't* scale it.  It comes down to mostly to two factors: quality of the source and the algorithm chosen.

Source quality is not something you'll have control over with stock assets.  You'd have to make or pay for something better.  Note also that quality has two sides to it, the subjective/artistic side and the objective facts like the resolution and color depth.  Both make an impact on scaling.

What can be controlled without getting new art is the scaling algorithm.  I suspect that most people scale using Nearest Neighbor, which will give you basically the sharpest conceivable result with extremely blocky pixels.  Personally, I find this a very crude result which gets worse and worse the higher you raise the scaling factor.  (2x is not that odd, by 5x it's already ridiculous.)  That's not to say nearest neighbor is useless.  It's ideal for editing, at least, and it's the fastest performing algorithm known.

As an aside, anybody who thinks pixel art from the NES/GEN/SNES years was meant to have a sharp blocked look is mistaken.  All that art was designed with full knowledge that it would be displayed through a low-bandwidth composite NTSC/PAL video signal connected to a CRT television.  Both aspects blur the pixels substantially, smoothing out the otherwise obvious blocks.  On top of that, the scanline effect caused by interlaced video modes darkens the image on alternating lines since only half the lines are actively drawn in the current field.  People who grew up as CRTs were already on the way out don't seem to be aware of this, sadly.

Contrasting with nearest neighbor, you could make a decision in the opposite direction and use something like a bilinear or bicubic scaler.  These are relatively simple and common algorithms, but they're mainly designed with photorealistic scenes in mind.  They work poorly on pixel art because of its relatively low resolution and color depth, plus the simple reality that not every pixel should be treated identically.  Pixel art is highly contextual.

Due to that issue, a huge variety of upscalers were developed for pixel art, mostly by the emulation community.  Wikipedia lists a lot of them on this page: https://en.wikipedia.org/wiki/Image_scaling .  I recommend the EPX/Scale2x, 2xSai, hqnx, or xBRZ algorithms depending on the input art, exact effect desired, and personal taste.  (Though I doubt there is any scaler which will convince nearest neighbor diehards to stop staring at huge grids of flat squares on their 1080p+ displays.)

Performance isn't usually *too* much of an issue in scaling, but if it is, there's three different things that can be done about it.  One, switch to a faster algorithm (or one with a better optimized implementation).  Two, implement the scaler on the GPU instead of the CPU, where it will be drastically faster.  Three, choose a fixed output/runtime resolution, stick to it, and prescale all your assets so that you can draw the result directly from storage instead of doing the computation later.  The third option has the disadvantage of not being able to change resolution or scaler, but it's by far the fastest of this group.

Just to add to what kagerato's had already said, the scaling algorithm is what will determine how the art looks when scaled or rotated.   Nearest neighbor and bilinear filtering are by far the most common and if you are scaling the image 'in engine' than one of these most likely what you are getting.   There should be some way to control which filtering algorithm is used, but where that control is will depend on what API/engine you are using.  You'll need to check the docs for that.

If you're doing the rotating in MS Paint, there should be some option for what scaling algortim to use.  If not, as Magic105 suggests give another paint program a try.  Gimp is a good free one.  Paint.Net is another one you might try.  It's more like MS Paint than GIMP, so might work better for you if you are already comfortable with MS Paint.

Two notes about scaling and rotating with bilinear of other filtering techniques:

These techniques compute the scaled/rotated pixel colors by averaging pixels around a given spot in the original image, INCLUDING TRANSPARENT PIXELS!

Note that in a standard 32bit RGBA pixel (the kind used by most paint programs and game engines), transparent pixels still have color values even if you cannot see them.

These values can 'bleed' into edges of the image when scaling or rotating using bilinear or other 'averaging' type filters.   

To take an example from my own experience, imagine you are working on a little 2D character sprite.  Rather than working against a blank background, you fill the whole canvas solid green (color 0,255,0) and draw the sprite on there.  Then you select all the green pixels and 'delete' them by making them transparent.

Trouble is those green pixels are not really gone, their just set to transparent.   If you rotate the sprite using a simple bilinear filter, suddenly the character sprite starts picking up green all along it's edges.

That's because the algorithm is averaging the invisible pixels along with the visible ones!

Gimp doesn't seem to have this problem with it's scaling filters (perhaps it ignores full transparent pixels when averaging pixels?) but from my experience hardware based bilinear filters (the kind your using if you do the rotations in engine) do.

There are several soltions to this problem.  The simplest is to flood fill transparent pixels black.  This isn't perfect but works better than green!

The more elaborate solution is to add color data to the transparent (invisible) pixels by averaging the color data in the surrounding non-transparent (visible) pixels.   There's probably some combination of basic select and scale or blur operations that could produce this effect for you in Gimp, photoshop, etc.   Since I am a programmer, I have just written my own program to do it.

Finally, if you are doing the rotations in MS Paint, etc, I've heard it suggested that the best results can be had by first scaling the image by 2x, then doing the rotation, then scaling back down to 1x.

Haven't personally explored this idea, but it's certainly worth trying to see if you like the results better.

That's a good point, capbros.  I forgot to mention the possibility of alpha channels/transparency.  Generally I go out of my way to remove an alpha channel from a sprite/tile sheet (if it had one to begin with).  That way you get more obvious behaviors by default.  Most editors have options that can be configured on the export or save menu/sub-dialog which will strip alpha (for formats like PNG or TGA that support it).

@kagerato:  When you pull the alpha out like that, what goes in the empty space?  Is it just black?

It depends on the image editor and its configuration.  The most common case I've seen is ARGB32 where alpha'ed pixels have a color already and retain it (the invisible becomes visible, essentially).  If that color turns out to be something strange, you then have to fix it.  Usually it's black, white, magenta, or some other stark background color that is easily replaced as necessary.  The editor generally takes care of reversing pre-multiplied alpha, if the image is being stored like that.  Many storage formats, including PNG, avoid premultiplied alpha by design because it can lose valuable information about the (potentially multiple) transparency masks.

@kagerato:  Gotcha.  One thing I notice about the GIMP is that it seems to just leave whatever color data there was in place.  You can verify this by just using the color picker and clicking around the empty space.  I guess this makes sense from a certain point of view, but it can lead to a really messy set of invisible pixels, escpecially if you create and/or edit the sprite with transparency active.

Do you by any chance know of a plugin, filter, script or combination of them that would achieve the 2nd solution I mentioned (filling invisible pixels by averaging neighboring visible ones)?

@LimbaJoe: Glad you like the GIMP!   Your character looks great!   Does she collect apples in that basket?  

@capbros :

That can (and often does) create a mess, yes.  That's why I recommend taking care of the alpha issue before creating or editing, to prevent the problem from compounding into the future.

As to your question, off-hand I can't think of a plugin or script that does that.  There are so many out there that I wouldn't want to say that it doesn't exist, though.   Undoubtably, GIMP is capable of it.

Unless I'm misunderstanding something, though, that task may not even warrant writing a script.  Try duplicating the working layer, erasing the inner content using select-by-color or fuzzy select (probably with a selection shrink), blurring the residual edges, and then adjusting the layer opacities and blend mode until you get the result you want.

Note that any form of averaging filter, fill mode, or blends pretty much necessarily introduces new colors that didn't exist before.  I wouldn't use a technique like this in any graphics that need to obey strict color palettes.

EDIT : Some searching a bit later lead me to this thread : http://www.gimptalk.com/index.php?/topic/46314-how-to-get-average-color-... , which may give you some more ideas about how to accomplish certain effects.  The sg-mean-fill script is available elsewhere : https://chiselapp.com/user/saulgoode/repository/script-fu/wiki?name=sg-m... .  It's probably not exactly what you want, but studying scripts is an excellent way to learn techniques that will gradually get you to a particular goal.