Most of their stuff is challenging at least in part, so I'd say choose the song(s) you most want to play - it'll help with motivation.

That said, the first satch tune I picked up was 'always with me, always with you', and the first Vai tune was 'for the love of god'. Both are easy to start with, and have nasty bits...