Flash, but use redundancy. Using a library such as SWFObject, you can dynamically load a flash file on top of another element (also called "alternative content"). There is a good tutorial on this which you can find here (it is also listed on the SWFObject website).
So, why flash and not gif? Essentially, this is because of the alternative content solution described above, as you get more versatility in what content you deliver. Mobile users, for example, are going to appreciate a static image (or nothing at all) instead of an animated gif.
Having said that, you will also be able to deliver better animations with flash. And, under certain circumstances, you'll be able to match (or even better) the .swf filesize with the .gif for the same animation.