Leo Breiman, the author of the Random Forest, discusses approaches to learning from unbalanced data sets in this paper.
The key takeaway: you need somehow balance data prior to feeding it to algo because if you do not do that the algo will lean towards making "right" decisions in the majority class at the expense of accuracy of predictions for minority class.
From practical standpoint, learning on equally balanced classes always improved overall accuracy on the original [unbalanced] data set in my ML exercises.
All in all, your intuition about downsampling the majority class is right. If you are at the model selection stage, I would even think about going further and starting with 10'000/10'000 test size (subject to # of features and available computational power).