Ew, K-ON! was pretty lacking in terms of plot for me. Also, agreed very much with Noir and Akira - Akira was a pretty amazing film. And I adore Miyazaki.
I'd always recommend Baccano! - mobsters, mysticism, and general free spirited life at the heart of it, with a late 1920s/1930s jazz influence. It's just completely confusing as hell.
Another anime - Durarara! was made by the same company, set in modern Japan, but it's slower paced, but more creepy and with fleshier, darker characters. Those are two anime I recommend to everyone.
-----
For your tastes?
I also might recommend Blood+, which is a nice supernatural anime with lots of twists.
CANNAN is an action-filled assasin based anime, interestingly set in Shanghai. Quite nice.
If you also enjoy some mech-based things, try Neon Genesis Evangelion. Incredible characters, incredibly messed up. I'd also recommend RahXephon, which is very Evangelion if the writer hadn't been severely depressed or lacking at funds at some points - less artistic, probably, but still great.
Also, if you're going to watch Mech-based things, you might as well watch Eureka 7 and Full Metal Panic!. My favourite sci-fi anime as a whole is still Ergo Proxy, so I can't help you there.
Darker Than Black is apparently quite good, although I haven't watched it myself to say whether it's cheesy or not.