I started with SPDs on my first bike and they were pretty fucking simple. 5 minutes practicing and I was good to go. I had only one OH SHIT moment. I did find out from my LBS that the SPDs are more MTB than road bike, so I bought some Sidis and put on the typical cleats on. I didn't buy the lollipop type of clipins. Again, not as bad. BUT, you have to make sure to keep covers for your shoes whenever you get off the bike or else: 1) You can potentially injure yourself, 2) You will destroy the cleats and won't be able to clip in (I rode from SF to LA and could NOT clip in d/t this).
In short: SPDs are a great introductory clip-ins, but are not necessary. Cleats or lollipops are fine.