This is a common question, and something I thought about when I first started pushing on Allen's work. The big push works for some people, and there are very good reasons for doing it, as others have mentioned.
I'll suggest this:
0) Get your supplies, and ensure you have good filing available (swivel distance, etc.)
1) Do a brain dump and build up the four key action categories: Projects, Actions, Waiting for, and Calendar. Most people already have a calendar, but they don't quite use it consistent with GTD, so go through it as well. 1-2 hours. Optional: Start your Someday/Maybe file.
2) Create clean project folders as you encounter them while working your new system.
3) Put all the stuff on your desk into a box, labeled "To Process." This is your top-priority stuff to go through. If you know some of it is "hot," pull those aside in support of 2). Put them in a folder labeled "Temp Action Support." This will be the first place you look for paper you need. It can also put your mind at ease that you're not losing anything important into the box.
4) Make a project to go through your paper backlog. The next action should probably be arbitrary chunking, e.g., "process next 20 items in To Process," or "spend 30 minutes processing..."
You should also start on your email. Use one of the two options Allen recommends re: folder setup (@Action Support + your list-making system in 1, or @Action + @Waiting for). Do this first, in parallel, or after 0-4 above.
I continue to work on a Kaizen approach to adopting GTD, but this is a quick sketch... Hope that helps!