Say for example, I have a signal with maximum frequency at 600Hz, and I originally oversampled it at 2000Hz. Afterwards I was only interested in frequency less than 500Hz. I guess I could first filter out frequency >500Hz, then downsample by taking every second sample point; or I could first downsample by taking every second sample, then filter out frequency >500Hz. Is there any problem with the two methods? Do they generate different results?
Yes, the order does matter.
In a real system with noise (as opposed to an idealized model) if you decimate before filtering, all the noise in the bands you aren't interested in will alias back in, raising the noise floor of your system. In your example, if you downsample by two before filtering you would have twice the noise in your bands of interest compared to if you filtered everything above 500 Hz then down-sampled (note this does assume a perfect filter, in reality some noise in the stop-band will still alias in but not nearly as much).
Even in an idealized model, if you downsample before filtering you will get aliasing from signals above the Nyquist rate. In your example, everything from 500 - 600 Hz would fold back in from 500 Hz to 400 Hz (e.g. a signal at 525 Hz would fold back to 475 Hz). If you filter first, you can exclude those signals.
Also note that in your example applying a low-pass filter with a cutoff of 500 Hz would not do anything after downsampling because now all the frequency content above 500 Hz has already aliased back down below 500 Hz.
In Short: The order does matter.
Downsampling by a factor of 2 without filtering, will cause aliasing in frequencies of 500Hz and more.
Since your signal is bandlimited to 600Hz, the frequency range of 400Hz-500Hz will be corrupted.
So (theoretically) the frequency range 0Hz-400Hz will be the same with or without filtering.
If you were only interested in this range, it would have been possible to avoid the filtering.