Is there a particular order in which to do feature selection and sampling?
In my opinion, the methodological correct way to do it would be to first randomly select the observations (e.g., with stratified random sampling to sustain the class balances as in the original data) and then do any model building (feature selection is a part of model building) based on the sected examples.

You should asses the quality of your model with remaining observations that have not been used for either selecting features or training a model.

Hope this helps.