Andres Segovia is fantastic, as is John Williams (not the composer). Also (although he is jazz rather than classical) you may enjoy Django Reindhart.

As for learning the guitar, i would recommend going into your local music shop and ask them to help you choose a nylon string guitar, this will give the sound you describe and most shops are very helpfulto beginners. Buy the nicest feeling (in playing position) guitar you can afford within your budget also get a spare set of strings (the shop will advise on which ones although do not skimp on these as good strings are very important) and a book aimed at classical guitar.