Random's tutorials are very good, though at the moment I'm making more headway with Lena's (linked above on tuts4you). This is probably because I'm still new to assembly language and Olly/idb.

The canonical intro book I recommend is Practical Malware Analysis (No Starch), with their debugging and IDA books as supplements :) http://www.nostarch.com/malware