"bcrypt предпочтительней в первую очередь из-за скорости вычисления" - да. "к неподъёмному времени взлома" - это зависит еще и от выбора паролей.

"Тут или городить капчи, или бороться с кол-вом коннектов в единицу времени." - да, но еще нужно учесть что у сервиса и до внедрения "тяжелого" хеширования паролей почти наверняка были другие аналогичные с точки зрения риска DoS слабые места, так что чтобы не сделать сервер более уязвимым к DoS достаточно настроить хеш так, чтобы он не был медленнее обработки другого самого медленного запроса, также доступного до аутентификации. Например, переход с быстрого не-парольного хеша вроде MD5, занимавшего 1 микросекунду, на bcrypt, настроенный на время 10 ms, на типичном веб-сервисе не повысит уязвимость к DoS (зачастую найдутся и другие запросы, занимающие 10+ ms или требующие больше I/O), но замедлит подбор паролей по украденным хешам на порядки. А с DoS можно бороться отдельно, для всех типов запросов.

"сперва проверять md5 вариант, если он корректен, то уже делать проверку bcrypt'ом" - это бессмысленно, так как атакующий сделает то же самое и получит не меньшее ускорение. Быстрый хеш, даже усеченный, хранить не следует.