you could try adobe premiere which have many effects to choose from. let your imagination go wild and start reading the manual, it's not an easy task creating an intro like the above, think of it like photoshop, you've got to know what you're doing and there aren't any standard tutorials to learn from.
find some movie samples and experiment, im sure the creators will guide you to the right path if you need their help :)
Well, you can do both intros on "basic" programs such as Sony Vegas. Could be a bit difficult but it's indeed possible doing it there.
All through, I made mine entirely on Adobe After Effects.
Pretty sure kab did his on After Effects also.
They key is mainly to have some knowledge about 2D animation. Once you dominate it, you can do awesome things on it. It's just a question of practicing and be creative.
ERRzyx your is so much better :/