Some very good hints in here. I think the part where I differ most is that I'm a huge proponent of OmniFocus. It's quite a complex piece of software, but it is also very well designed, so you can put together a lot of different workflows and be mostly keyboard driven.

Being able to cross-reference projects/contexts with easy filters for next action or ticklers is invaluable. Repeating events and automatic review scheduling are the icing on the cake. I believe in GTD enough that I would still do it in pure paper format if I needed to, but OmniFocus can remove most of the overhead which makes it all the more attractive.

It's a good enough program that I'm contemplating switching from Android to iPhone just to have it on my mobile.