A simple sponge routine is very easy to learn, but you'll need a fair bit of practice.
There are actually a lot of different moves you can do with sponges, but you can have a great routine with only a few.
The "Earplugs" video/DVD (wish I had it on DVD

) by Jay Sankey is good. It's a nice, funny routine and will teach you some good sleights. You also get a nice "big" finish.
You can even buy yellow sponge balls, so you can do a shapechange and then move into a ball routine. Then of course you could do, for example, a "Spellbound" change and use red balls, leading into cubes, a large ball, rabbits or whatever.
You asked what size and type. I'd say that, if you can, use 2" ones, rather than 1 1/2" ones, simply because they are more visual. You might find them a bit too big for your hands, but you need to try. I don't have big hands and I find Gosh 2" supersoft sponges fine for most purposes.
That sort of gives you a clue as to my answer for your question about what type. Some sleights are easier to do with the regular density sponges (Spellbound would be one, I suppose), but I think the majority are better with supersoft ones.
So, I suggest your first purchase is a set of red or yellow 2" supersoft sponge balls. Try them out (Gosh ones have a basic routine in the packaging, or they used to). If the sponges are too big or too soft (or both), you can get another set.