Image transforms like scaling and rotation can degrade images, and involve trade-offs between artifacts like aliasing, blockies, blurring, edge halos, ringing, and moire. Background on image transform can be found at Cambridge in Colour's Understanding Digital Image Interpolation, Optimizing Digital Photo Enlargement, and A Closer Look at Resizing an Image for the Web & Email.
FxGuide posted a comparison of transforms in hi-end apps (including AE) and concluded there is no single magic bullet to automagically improve quality for every image, or a single approach for every app. It does help to use high quality scaling and deinterlace algorithms, pre- and post-process with blur (when scaling down) and sharpen (when enlarging) filters, and deartifact or denoise with a specialized filter (or with AE Remove Grain or by brute force with a Median filter). You're on your own when animating slowly from 98% to 102%!
Some applications take scaling quality seriously, though many desktop editing and compression software does not. AE uses simple bilinear interpolation, or a weighted box filter, even at Best Quality. Applications that use bicubic interpolation and variants include Photoshop, Commotion, Shake, or Combustion. The semi-official workaround, AE's Magnify filter, is not a solution, although some filters that scale may use high quality algorithms. Note that resampling in AE when there's no geometric transform is due to subpixel positioning. You can avoid this by positioning layers in 1 pixel increments.
You can access different scaling algorithms inside AE by using Resizer from Digital Anarchy. ReSizer also has a deinterlacer that uses motion estimation. Check out DA's before-and-after mug shots, though they don't compare results with the better algorithms in Photoshop.
Other AE filters that offer transform and enhancement features include Algolith, Topaz Enhance, and others by RE:Vision Effects or Red Giant Software. Debabelizer ("Sharp Sine" scaling on non-interlaced footage), IrfanView, and Satori Paint are also said to be good. Fractal-based PS plug-ins like Genuine Fractals (better with flat colors or clean images), PhotoZoom Pro or Pxl SmartScale sometimes work well. Digital photographers have investigated different methods that may be better than the fractal filters -- see the solutions from Fred Miranda (FM Stair Interpolation, Resize Pro) and tests from Roger Cavanagh.