It kills the "pixelness" of it, yes. Personally I do like them though. Those algorithms do create interesting looking graphics. Last year, me and my girlfriend decided to play some classic Mario again, and since we didn't have any old Nintendos nearby we used SNES9X which uses, I think, hqx. It's different but quite neat.

For making a dedicated pixel art game they're unusable though.

There was a cool SIGGRAPH 2011 paper from Johannes Kopf from Microsoft Research and Dani Lischinski from The Hebrew University that presents a new pixel scaling algorithm that really takes pixel scaling to a whole new level. Check it out here: http://research.microsoft.com/en-us/um/people/kopf/pixelart/

Actually the worst thing is just linear interpolation.

Why so many emulators default to that is mind boggling.