Rules of Thumb
Are there any good rules of thumb for modeling spreads over the short-term? Sure. Consider the time of day, size on the bid vs the ask, minimum price increment, and volatility. Will you get much more than that here or anywhere? Doubtful. Moving beyond those basics is firmly in the land of secret sauce and anything public is unlikely to be helpful.
Rapidly Changing Features
How to handle financial features which change quickly? Some aggregation might help and some recent history might help. Sometimes how you work with features or scale tham makes them more or less stable. Again, this starts getting into secret sauce: nobody who does this successfully is going to spill the beans publicly to make your life easier (and consequently make their life harder).
Are Spreads Noise?
The fact that you think spreads at $t+\Delta t$ are unrelated to spreads at $t$ tells me you are not thinking about why spreads exist and their underlying meaning. If you do not understand your data, it is going to seem confusing and look like noise. Spreads are not noise nor are they unpredictable. However, these predictions can be worth money and the market is competitive, so you should not expect fantastic predictive ability.
Suppose spreads were just noise. Making money should then be simple: place bids and offers a bit away from the current midpoint, wait to buy or sell at an excellent price, and profit! One problem is that if people trade based on information (which they are incentivized to do), you may buy when many want to sell due to bad news -- or sell when many want to buy due to good news. Another problem is that other people will compete to do this. Since spreads come from potential buyers and sellers, quickly analyzing shifts in their supply and demand will help predict how spreads change. If that is true, then spreads will no longer be noise. So... proof by contradiction: spreads are not noise.
Understanding the Fundamentals
Unfortunately, you are trying to understand data that is probably among the more mysterious data in finance. We have lots of ideas about what companies should be worth, the value of a stream of cashflows (even risky cashflows), and how to create a good portfolio. The models for these usually give us answers that are very similar, especially over longer periods of time.
We have fewer ideas about the strategic interactions between potential buyers and sellers, different concepts of liquidity, what leads to an actual trade, and how these behave over time. Theoretical models often only show that one particular force is relevant. That means that data analyses have to combine these ideas based on the purpose of the analysis. Furthermore, different analyses may come to different conclusions depending on which forces are dominant over the short time period being analyzed.
Market Microstructure
The field that analyzes those forces is market microstructure. If you want an analogy, microstructure is to finance as particle physics is to classical physics. I know this seems like just a machine learning problem to you, but having seen many people fail with an approach like yours... I suggest that pounding more data through the latest ML techniques is not likely to be successful. My advice is to work smarter.
You would do well to spend more time reading up on market microstructure and less time trying to stumble upon relationships people have already discovered and written about. Yes, imbalances and other metrics change quickly; that is why HFTs need to be quick. Your modeling cannot ignore that without suffering. I would pick up Foucault, Pagano, and Röell's Market Liquidity and maybe Johnson's Algorithmic Trading & DMA.
Feature Selection/Model Selection
Finally... I will say something I have said many times: feature selection (aka model selection) is NP-hard and not a solved problem, so there is no algorithm to give you the best model. That has been known by people in OR and statistics for decades and ML researchers have found no differently; otherwise we would not still be developing new tools to improve model selection. Model selection is still an art informed by knowledge and experience.
While that means part of your question cannot be answered, you should be happy about this. The unsolved nature of model selection means that if you are a good analyst, you have good job prospects for a long time.