Next up is caching is_search(), is_feed(), is_single() etc. Where should those be cached? The “init” action is too early for is_search and probably others but I don’t want to depend on actions that may not be in a theme.

You should use the ‘wp’ hook for this.