How to display high frequency signals on a small display?
This is a problem with many aspects to it, but at the very minimum, you should not be tying the number of samples you take to the resolution of your display. Instead, take samples as fast as you can or, if you have an analog anti-aliasing filter (as you should), at or above the Nyquist rate for the filter's bandwidth.

Then, when you paint the samples you have taken on the screen, you can choose how to do so. Some simple to implement ways:


For each column of the screen, find all the samples which fall into that range, and fill from the minimum level to the maximum level of those samples. This will avoid creating additional aliasing, and is a common display technique in audio editors.
Draw all the samples individually as points, no matter how many points end up on the same column. This shows more detail but requires more interpretation from the user.


Besides avoiding unnecessary aliasing, separating sampling and display also allows you to implement single-shot capture followed by zooming/panning the view, which will help with the usability of your low-resolution display.



As to auto-ranging: once you have sampled as best you can, you can then apply your frequency counting or whatever other algorithm to that data to choose a starting zoom. But if you sample slowly then you have already thrown out data, and that's a problem. (You might have a problem with storing enough data to work over a wide frequency range without external RAM, though.)



Depending on your goals, it might be an interesting exercise to implement an oscilloscope on a PC using sound-card input. That way, you can play with signal processing and painting algorithms with fewer resource constraints; and USB sound-cards can be readily found with up to 192 kHz sampling rate (though often AC-coupled). Then you can take what you learned and figure out how to fit it onto the Arduino.