Omohundro has a paper on instrumental goals that many/most intelligences would converge on. For instance, they would strive to model themselves, to expand their capabilities, to represent their goals in terms of utility functions, to protect their utility functions against change, etc. None of these are universally true because we can just posit a pathological intelligence whose terminal goal is to not do these things. (And to some extent e.g. humans do in fact behave pathologically like that.) We can say very little "optimizers over possible futures" in full generality, because that concept can be very broad if you define "optimizer" sufficiently broadly. Is a thermostat an intelligence, with the goal of achieving some temperature? Or consider a rock - we can see it as a mind with the goal of continuing its existence, and thus decides to be hard.

Yes, at least some of the time. Evolution fits your definition and we know about that. So if you want examples of how to deduce the existence of an intelligence without knowing its goals ahead of time, you could look at the history of the discovery of evolution. Also, Eliezer has has written an essay which answers your question, you may want to look at that.