Start with the Uno. You'll cut your teeth on all the same conceptual ground you'll encounter with the Due, but you'll have a simpler platform under you with a great deal of supporting information available on the Internet.

When you grow out of the Uno, the Due will be there waiting for you.

Personally, I'm going to avoid getting a Due until I need the extra horsepower. The simplicity of the AT family of microcontrollers is very appealing. Once you have a prototype working on the Uno, creating the deployable version using an ATTiny85 or whatever is not that difficult.

Compare hooking up an 8 pin ATTiny85 and a few supporting components vs the soldering wire-wrapping nightmare of using a AT91SAM3X8E or some near equivalent.