Among the best (and most expensive) are Sorenson Squeeze, Grass Valley ProCoder and Autodesk Cleaner. Xilisoft makes some cheap converters that are ok, but I've found their software slightly buggy although it does work. There's a good free one out ther, but I don't recall the name right now so I'm sure someone else will chime in. If you do have the money to spend, I'd still suggest one of those first three since you generally get what you pay for with free stuff, although the one I'm trying to remember is pretty good.
By the way, I'm sure you know this, but just in case ... although you can convert mp4, etc. to an uncompressed codec, doing so doesnt regain the original uncompressed quality. And, AVI is fine to work with in AE, but it isn't really the "best" ... that would be QuickTime.