Fpgas don't care what bittage cpu they're connected to. The main issue to contend with is that most fpgas will have trouble interfacing to 5V logic. So to get around the issue of level translation, you generally use a 3v cpu. With that in mind, do a search on the web as there's heaps of people selling little boards with fpgas and the bare essentials for the purpose of education. For a start try the vendors themselves and www.parallax.com. As for which brand - Xilinx or Altera (and whoever)? Toss a coin - the two majors are much the same (their marketing guys would tell you different). At the entry level the major stumbling block is the learning curve to use the tools - the devices themselves are like a box of Lego - the skill is in putting the pieces together.
Xilinx had (or still has) a book & software that was pitched at the universities which was a very good introduction to cplds and fpgas. It worked for me. I bought it from Amazon.com about 5 years ago. Whilst the devices in the book are a little dated now, the concepts are the same.

Have fun!