Great thread.
I'm always looking for animation recommendations, as well.
Edit: Whoops, dunno how similar all of what I wrote about is to the videos you posted, as I've not seen either of them, but they're both directed by Makoto Shinkai so maybe check out his other stuff like Voices of A Distant Star and Children who Chase Lost Voices?
In terms of anime movies there's Redline (which is sort of infamous for its long development, being hand-drawn). It's certainly style over substance but
definitely worth checking out for its animation. As others have mentioned, anything by Satoshi Kon is worth watching, Hosoda as well. Tekkonkinkreet is quite good, too. Then there's also stuff like Macross: Do You Remember Love, Angel's Egg, and Metropolis. Anything by Studio 4C is generally great in terms of visuals (I haven't had the chance to see the Genius Party shorts yet, but I really like Koji Morimoto's work in general). Masaaki Yuasa's work always has interesting visuals in terms of art style and animation (Mind Game, and for series Kaiba and The Tatami Galaxy). Also, I've not seen them yet but some movies I've been meaning to check out are A Letter to Momo and Wanpaku Ouji no Orochi Taiji (the latter seems to have inspired Wind Waker's art style). As for anime series, I'd highly recommend checking out Denno Coil. The first few episodes in particular are really impressive. Also, it's an older series, but if you're into Miyazaki there's Future Boy Conan.
I don't know that many animated shorts off-hand, but there are lots of really impressive ones around. I really like this one:
Flooby Nooby posts a lot of neat shorts and other animation related stuff like pencil tests. Also, pretty much all of the Gobelins student shorts are amazing - France in general seems to put out a lot of great 2D animated stuff. I don't know that much about Western 2D animated movies (other than, like, The Triplets of Belleville) to be able to recommend much. I did see Le Jour des Corneilles, though, which was gorgeous.
Paprika gets a big +1 from me. That opening sequence still blows my mind.
I love the opening of Paprika so much. The visuals and music go so perfectly together.