It's hard to tell you where to stay as I'm not sure what you are looking for. When I was planning my move, and even after I arrived, everyone told me that I "needed" to live in San Telmo, which I did. But I found that the best way to pick a barrio was to live in different ones for a couple of months at a time and decide for myself. Here's my advice anyway on the place I lived...
San Telmo: I found it to be a filthy, urine soaked, expat ghetto. But maybe that was just my part of San Telmo. I have friends who live there and love it. If you're in your 20's, laid back, enjoy bars, and meeting similar expats San Telmo is a good option.
San Cristobal: Very neighborhoody. Impossible to get an English newspaper there. Which we thought was awesome. Very few expats, if any. Quiet. Blue collar. Elderly. Not "touristy" clean, but clean.
Almagro: This is where we have been living for 4 years with a baby. Again, not touristy clean, but clean. Subway and bus friendly. Enough going on to keep it interesting, but not so much that you are constantly overwhelmed by noise and traffic. Easy access to bars, restaurants, theaters, and parks.
I haven't lived in these barrios, but have been here long enough to have formed in impression:
Once: No Way. Dirty and loud during the day. Dirty and dangerous and night.
Palermo: there are so many different parts to Palermo. Lots of international restaurants and bars. Big expat scene. Some parts are great if you're a character from Sex In the City or one of those dramas where teenagers look like 20/30somethings, have orgies, and drink martinis. Other parts are more family oriented and quieter. In general, Palermo is great for high-end shopping and eating out.
Villa Crespo: This is the new up and coming barrio. International restaurants are sprouting up, high-end shopping, and apartments targeted to professional singles. Not as fancy as parts of Palermo, and still maintains a bit of a neighborhood feel.
As for crime, I've only been pick pocketed once. It was in Belgrano (Chinatown) and was not an aggressive encounter. There is crime all over the city. Some target expats, some target posh neighborhoods like Palermo and Recoleta. A lot of crime is just opportunistic. Be smart, don't flaunt your camera, your phone, your laptop or your wallet. Don't do favors for strangers, etc. You're going to hear a million horror stories about Buenos Aires. Filter.
Send me a PM if you have any questions.
Thuy