I teach here in HI and when it comes to starting out there is no substitute for good instructions from a qualified instructor. That said, you can get a LOT more out of your lessons if you come into them with as much preparation as possible. By this I mean get the Progression DVD (as mentioned previously), watch as many YouTube videos as you can, and just do anything and everything to get familiar with the gear and basic techniques. That is what I did when I was learning. I was up and riding in one 3-hour lesson! I was able to skip over a ton of the "here's a kite, bar, lines, and how the wind works" stuff and get right to it.
Trainer kites are great, but there is no substitute for getting time with a real kite in your hands. Your instructor should be a great resource in recommending a suitable first kite -- or kites.
If you think that you'll be riding on land, that means smaller kites and possibly going with a foil instead of an inflatable. I personally don't like the effect that hard surfaces have on my body's softer surfaces -- water is much more kind! That said, not everyone lives in paradise, so I get it.
Nothing in this sport is particularly mind-boggling. A good instructor is going to break it down into fundamental blocks that you can then assemble into the big picture.
You can use just about anything to ride under a kite -- to include a wakeboard. Take a look at some of the crazy stuff Tophat rides out here at Mokuleia! However, a dedicated entry-level kiteboard makes it so much easier to get out there and enjoy the sport. Kiteboards are just about the only piece of gear I can endorse a newbie buying second-hand. Kite, harness, control system... all of these should be bought new the first time around. You don't know what to look for or what may feel 'wrong' if you get something used. While an experienced kiter could make it work, why frustrate yourself with gear that may no longer be ideal? Every year things get better, safer, easier. There are alternatives to the big expensive brands too (Switch, Best, Caution, etc). This forum is known for negativity regarding just about anything, so just remember that most anything you can buy new right now is going to be pretty darn good. For every piece of gear you search for you'll find people who will emphatically denounce it as 'junk' but just remember that most, if not all, new stuff is really awesome! Steer clear of gimmicks and you'll be rewarded with one of the most rad sports you can ever imagine! Welcome to your new obsession.