Yeah, it took me an hour or two of trying to kill the Eye of Cthulhu the first time as well, but once you get his attack patterns down, assuming you have enough time and potions (and shurikens, assuming you're only in starter gear), you should be able to take him down. Very, very helpful to have a large flat platform to fight him on so you can dodge.
The new potion/buff system makes it even easier - gravitation potion with a closed in large box so you can flip up onto the ceiling and down again at will helps a lot if you can control it. Ironskin and hp regeneration buffs are all that I really need, though - admittedly, I'm in silver armor and have 340 ish hp from the ton of heart crystals I keep finding, but still.
Eater of Worlds and Skeletron will prove far more difficult than the Eye, so get used to dodging a lot - you used to be able to just lure EoW back to spawn and just suicide kill him, but since he flees when you die now AND can only be fought in the corruption, he's a bit more difficult.
I personally rate Terraria as equal to Minecraft in how good the gameplay is, in my opinion. They're both slightly different takes on the same sort of genre, but both are extremely fun.
Only thing I really dislike about Terraria are those god damned bats that constantly swarm me everywhere. Just enough health to be a nuisance, do a decent amount of damage, too small for me to accurately shoot them down with a bow, and somehow they're fast enough to ram me when I try using my sword occasionally. Very, very irritating
Oh, and of course they have different variations just about frigging everywhere, so you can never really get away from them, either. Other than the dungeon, normal surface, and desert, they're everywhere or there's a different flying creature that's even more irritating to deal with (such as eater of souls swarming in corruption).