Another vote for "Skallagrigg". Unfortunately if you tell people what it's about they tend to think "sounds awful" and vow never to read it. Give it a go - it's one of a very few books that has changed my views on certain things.
George R R Martin's still incomplete historical/fantasy series "A Song of Ice and Fire" (the Borgias meet the Tudors) is well worth a go, even if you're not normally a fantasy reader. His "Fevre Dream" (a steamboat captain finds out that his spanking new boat has been sponsored by a vampire with a plan) is also a great novel.
Jasper Fforde's Thursday Next series (starts with "The Eyre Affair") about a investigator tasked with maintaining the integrity of fiction (such as keeping characters from sneaking into other novels) is playful and funny.
Philip Reeve's "Mortal Engines" quartet (a pair of teenagers try to survive in a post-apocalyptic world where cities are mounted on wheels) is supposed to be for the young adult market, but is far too good for them - the ending is stunning.