The obvious choice for me is Radiohead - there's virtually no indication on their debut Pablo Honey where they'd go over the next four or five albums, jumping to The Bends and then to OK Computer and then to Kid A (hell, even Kid A came as a surprise to a lot of people).

Also Super Furry Animals are a band I feel have improved with each album.