The first book of his that I read was "The History of the Siege of Lisbon". I had to read the first pages a few times before I could understand it all, but I ended up hooked. I've read almost all his books and finally got interesed in literature written in my own language. I prefered English and Spanish before he finally made me see how wonderful Portuguese is.
I am not sure if you are Portuguese or Brazilian, and this is probably way too obvious but... if you haven't: do read Guimarães Rosa.
Like Saramago, his writing takes a while to sink in, but once it does, you're hooked. To me he's the best Portuguese language writer in the 20th century.
