Oh man, can't believe I haven't mentioned Sting - Nothing Like The Sun. That was his second solo album.
Several hits, but I like every track on there, and the list of guest musicians that performed on the recording (and many of them on the live tour) is just incredible.
Branford Marsalis, Annie Lennox, Eric Clapton, Mark Knopfler, Andy Summers, Gil Evans, Kenny Kirkland.
I also really like Sting's first solo album, Dream of the Blue Turtles. It's probably a no-skipper for me, as well.