"Legal", probably iTunes or similar stores for music (and Video in the US, not yet offered in the UK). Napster has a good base from the converts of old now going above board.
I heard UseNext is supposed to be quite good (a usenet news group reader / downloader) but I havn't tried the service myself.
Not to cast a shadow on the software (since the torrent is a much misused legal outlet) but BitTorrent clients are probably leading the way for non-legal downloading.
I guess for videos Ant Video Downloader is the best. Easily download videos from a variety of streaming sites such as YouTube, Google video and save them to your hard drive.