What you say is correct. "consider doing something" means to think about doing it, while "consider X to be Y" is for when you have an opinion/belief about that thing. The correct sentence using the verb "be" would therefore be: Many people consider dogs to be "men's best friends".
New words, one handy idiom, and a 2-minute quiz — delivered to your inbox to keep your streak alive.
Tim Chen 8872Many people consider dogsYou may be interested in this post on object complements.