I think someone else already mentioned it, but Last Exile is definitely one of the best anime series produced in the last decade. I had a friend who was similar to you in that he was never really sold on anime, but wanted to like it and gave different shows chance after chance, and then I finally recommended Last Exile and he was hooked. So, at the very least, I know this series is a good one for hooking in the naysayers! lol
It's a good series for newcomers foremost because it doesn't suffer from the heavily clichéd anime tropes you see in series like Full Metal Alchemist, Evangelion and Naruto. I would say ignore people who have recommended Azumanga Diaoh to you as well, not because it's not a fantastic series, but because it plays heavily to anime tropes and is very set within the anime world in it's humour - from the outside it might just seem puerile or overly slapstick.
Another recommendation I would make is Hell Girl (Jigoku Shoujo). It's an episodic psychological horror series which I think is genuinely scary and manages to avoid most anime clichés. There is a good dose of Japanese mythology sprinkled throughout the series which, from a foreign point of view, is deeply affecting and helps to create the fear factor in its unfamiliarity. Great series if psychological horror is your thing, definitely.
Also, if you enjoyed Spirited Away then I wholly recommend you check out both Princess Mononoke and Howl's Moving Castle. Both fantastic anime films by Studio Ghibli; the trailer for Howl's Moving Castle (my personal favourite) is below.
Failing all of that... then I'd say go with my favourite anime series of all time which is Full Metal Panic. lol... it's probably not your thing, but this trailer makes it look awesome! xD. Basically, it's an anime series which takes the giant mecha genre and tries to make it more realistic with a militaristic settling and a more 'internationally aware' storyline.
