I love David Byrne's solo stuff. He has a new ablum coming out in a month or two I believe.
When he left the Talking Heads he went to the Latin/Brazilian beat. That is still in his music but less so. So, if you like the Latin/Brazilian beat (I do) I would say start with Rei Momo or Uh-Oh. If you want the music to have more variety I would say get one of the newer albums, Feelings. Miss America off of that album is great. His last album, Look Into the Eyeball, is also great and has a variety of styles, including a 60s vibe on The Neighborhood.