Hi Rasengan,
Welcome to the wonderful world of card magic

As said before, go for the Tally Ho cards. They are definately worth the money! I actually started with bridge size cards myself, because they don't sell USPCCo's cards in the Netherlands, and most of the non-brand cards are bridge size here.
Anyway, I think it is good to just get
any cheap deck you can find, just to
practice with. You can then use the Tally's to perform with, once you get the hang out of it. Especially when you are doing some hard sleights or fancy ways to shuffle cards for example (flourishes), your cards will be killed before you know it. I actually killed an entire deck, just to practice card springing and riffle shuffeling. So if I were you, I would buy a cheap bridge size deck and that more expensive deck of Tally Ho's.
Also, there are many things to start with for a beginner. Most of Ellusionist's dvds are for beginners actually. As said before, Penguin Magic's Born to Perform is a great dvd, but maybe a bit too hard for a beginner. You should check that one out once you know the basics. Also, Theory11 itself sells some beginner tricks. Check out the 1-on-1 section and look for Aaron Fisher's card fundamentals.
Good luck buddy, and let us know if you have any more questions
~Morphweasel