I watched the johnwayne movie and I'll try to give a few and hopefully constructive comments
It's good. But I think it could be even better.
The first thing is the AVI compression which kills all the details. Don't forget that you will put these videos on CD so NEVER hesitate to raise the detail quality at the expense of making bigger AVI files. The video quality was in fact quite ugly on this one. This is a problem because it's a pain to watch an ugly video. If you're short on disk space borrow your GF's new hard disk
The next big thing is the way to present the map itself. As others pointed out, it seems mandatory to present the map while players (or bots) are fighting. Hide, or better DO NOT show, any part that is criticizeable (such as the map being "flat" - present view angles that do not make it obvious. And abuse of the spectator mode. At least 2/3 of your videos should happen in spectator mode to show overviews of the map. This is very important. People want to see the maximum of the map in the minimum of time. Spectator mode is ideally suited for that. Make pauses when roaming around ; for example, pause for a few seconds over the map to show the scene with cactus in the middle of the street. And if there were bots fighting here at this very moment, that would be a great plus.
Identify the most beautiful scenes and visit them all one after the other in spectator mode. Never cross walls, even if you can, instead fly around the map like a bird would do. Crossing the walls will make the usual garbage display in the video, you don't want the guy to see that. If you want to record a part in first-person mode, to show how a player would "feel" the map, don't wander around aimlessly like you do but instead move tactically as if you were playing for real. Visit the best looking hiding spots, too. Don't shoot without reason either unless it's for breaking stuff or making a cactus dance
About the voice comments: insist more on WHY you designed things this way. Show the guy that you knew pretty well what you were doing and why doing it as you did was the best way to do them. SURPRISE him by giving him reasons that he wouldn't expect and that only you could know. Make him understand that it is a CHANCE for him to hire you because of this unique experience you have that you are willing to employ for him. Mention whatever detail in the map, and say: "here is [something]. I did it this way because .... and because ... If I hadn't done it, the map would have such and such problem." ALWAYS talk like that. ALL the frikkin time. ALWAYS DO THAT. The guy must be convinced that you are the best. If there are disputable elements in your work, do not show them. If you can't help, JUSTIFY THEM. Never ever ever ever let something unjustified - that would simply ruin the whole thing and blow away your chances. The guy would close the video, eject the CD, throw it to the bin and do something else.
Avoid to show parts of the map that feel "empty" or "unfinished" or somehow just too flat. Always show the parts that are the more richly detailed, the more richly textured. If the rendering speed is a problem in CS, show how you can exploit it at best. And don't forget to show that you can do something else, too. Be a perfectionnist when selecting the scenes to present. Never forget that the guy will watch this stuff in a hurry, between two urgent works, from a distracted eye. You must catch his attention. The beginning of the movie is REALLY good for that: "welcome to cs_johnwayne" with the ambience music in the background... perfect

The music should last longer and the same rhythm should have been kept for the rest of the presentation. Unfortunately there's a sort of "slowdown" in the tempo which makes the interest go lower and lower... and eventually vanish away before the video ends
That's all I can think of. Best quality AVIs, spectator mode, firefights, rich scenes, and: "I designed this part this way because ..." Let this be your credo and I hire you by the end of the first video I see
