What hook is most appropriate for code that should run as early as possible in bootstrapping but only on certain paths? I am writing a module that should run code as early as possible because it's a conditional redirect to another page, so the first page doesn't need to finish loading.

I only want to run it on /foo/*. 

Is there a hook that can be bound to a particular path, like hook_form_alter() can be with form IDs? Or should I just use hook_init()?
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.