Shots won't be helped by the ISO 800 with a small sensor like that camera has. Also snow and /or white clothing "fools" the camera into thinking the scene is brighter than it really is if metering is set on average. Use spot metering if available or centre weighted at least. Camera may have a "snow scene" program. Also select single focus point if possible. Thus allowing you to focus on the subject, lock focus and recompse.
Any reasonably modern DSLR will be better in terms of noise and image quality. There's a big choice, and little in real terms to choose between the main players.
You also might consider some of the later type "point and shoot" cameras which have larger sensors and are more "pocketable". Sony RX100 in it's various incarnations is one, but there are others.

What model camera do you have? What ISO were you shooting at?

Getting back to your original question... there are numerous causes of grain/noise... having to brighten the image in post because the original was under-exposed is one possible cause and given the snow in the background of your shot, I wonder if that's the problem here. Spot metering would have helped there.

Alternatively, if your camera is a few years old and you were shooting at a high-ish ISO, grain might be inevitable even if you get the exposure right in-camera. Is the problem so bad that using noise reduction in post doesn't fix it up to an acceptable level?

Some good cameras there. The full frame cameras tend to be bigger and heavier (some much bigger and heavier!) and more expensive. They need good glass to give the best results (think bigger, heavier, and yes, more expensive). The later "entry level cameras, like the D3100 (think I'm right on that), and the Canon t3i tend to be a bit light in construction. They still need decent glass to give good results.
There's no right choice as such. If I wasn't "a photographer" and didn't want or need interchangable lenses, and wasn't bothered about an optical viewfinder, there are all sorts of options these days. Hence the RX100. I became sick and tired of lugging a big bag of gear around all the time. Another option is something like the RX10. A "compact camera" with 24-200mm lens. Decent stills output, and apparently outstanding video output.

Quote from: ArenaCreative on January 13, 2015, 11:35

My recommendation is to stick to the XXD series to start, just because you are getting a solidly built camera body made of magnesium that also fits larger hands a lot better than the Rebel series.  The rebels are plastic, but also solidly built.. but no review wheel controls on back, which was also deal breaker for me.  With the XXD series around the same prices as the rebels, used... it all comes down to personal preference.  Nikons are just as competent.  I just went Canon because I could swap lenses with my friends.

Thank you! He says it has the 28-135 3.5-5.6 VR lens and he's thinking around $500 :/

You'll drive yourself mad with reviews and specs! I doubt if there's much to choose "real world" image wise.
http://www.dpreview.com/ have probably some of the best "Hands on" reviews, with sample images.
At the end of the day though pretty well any modern DSLR will give you decent images. What other features you want, and the depth of your pockets will decide your final choice. Remember that the quality of the lenses used often makes more difference than the body used.
Also remember there are makes other than Canon and Nikon. I use a Pentax DSLR. There are also a lot of people out there on the internet seemingly trying to justify their own choices. 

I would get the Fuji xt1 if I were starting again. Fuji's best lenses are top notch and not very expensive compared to Nikon or Canon.