Probably the feature I’ll use the most out of the ones they recently debuted will be the URL investigator. Plug a URL into the search box at All The Web and it returns a bunch of information, including how many external pages link to that site, how many pages are indexed by that domain, who owns the site, etc. There’s even a link to the Wayback Machine so you can see what a set of pages used to look like.
Google provides the most useful of these features, too (including their own cache), but not nearly as intuitively as AllTheWeb does.
Examples: