My personal favorite's not in order
Stein's;Gate
Ghost in the Shell
Haibane Renmei <--has music done by the person who did SoTC soundtrack kow otani
Monster
Planetes
I love Serial Experiments Lain, and Texhnolyze. But, I really wouldn't recommend them to someone coming off watching Persona 4 and FMA:B. Those two are very inaccessible, and might just frustrate someone getting into this stuff.
Don't watch the original FMA, I know some people who thought less of the Brotherhood, by being tainted viewing the original series (which is still pretty good).