Madlax has one of my all time favorite opening themes. Musically perfect, incredible lyrics.
For closing, I'd say Bleach has one of my favorites. Again, Musically wonderful.
Other series to check out based on opening and closing...
Fullmetal Alchemist has the best openings in all of anime. This is indisputable FACT.
For openings and closings of good quality the whole way through, Slayers. Megumi Hayashibara is definitely awesome.
Although there haven't been that many openings for it (for a 200 episode series, that is), I've downloaded each opening for One Piece, and 3 of the 4 are constantly being played on my playlist: We Are, Believe and Hikari e are all wonderful pieces of music.
Best Anime Closing Ever: Dragon Half. Watashi no Tamagoyaki. That song is so much fun.
Even with my limiteed viewage of Evangelion, I will say that Cruel Angels Thesis is another classic opening.
And finally, Excel SAga, for the quirky opening and adorable ending.