To me they are different. I don't think I would ever use your second sentence.
We should consult a doctor. = We should obtain professional medical advice from a doctor. The doctor will tell us what is wrong (make a diagnosis) and tell us what we must do.
The use of "with" suggests a discussion in which various opinions are voiced (often by a nu