What hook is most appropriate for code that should run as early as possible in bootstrapping but only on certain paths?
Similar to the forms, there's hook_page_alter(), but that happens near the end, making it a bad place for redirects.

hook_init() should be fine, but is not invoked on cached pages.

hook_boot() sounds self-explaining; it's run so early that you can't call any module's function, not even drupal's.

however, since you need a conditional redirect and you already have your own module, just add it atop the page callback of 'foo/*'.

if that callback it's not defined in your module, use hook_menu_alter() to have that path pointing to a custom function that will execute your conditional redirect.