Hi Julie!
Just wanted to add my story of cats N dogs. My oldest cat was an adult and sort of dog-savy when we first got Max, and initially Max chased him a bit which we squashed. Much later, when we were thinking about getting Star (Dane), we had a home visit from the adoption agency where the lady brought her Dane so we could see how big he was. The visiting Dane wanted to head up the stairs ('cause he wasn't allowed up the stairs at his house) and I knew the cats would be hiding up there. The visiting Dane ran up and down the stairs a few times, then went up once more and stopped halfway. There, halfway down the stairs was my old cat (about 10 years old or so), hissing and turning sideways. Apparently, my cat DID NOT want that dog upstairs and knew how to stop it! We knew then that we didn't have to worry about him and a new dog.
As long as you have a safe place for the cats to go, they'll work it out with a new dog one way or another. My current oldest cat has lived with Max for 15 years, and STILL hisses at him every time she sees him. Max just ignores her if possible, and defers to her when not.
Good luck!
Tracy