You can definitely take cities that start off at 40% or 30% culture penalty.

"Previously, I've just been using the other culture's buildings and bonuses to train and retrain my troops. No wonder I've been having some issues with public order.."

Yeah. I always knock down the temples/taverns type buildings in the towns I take over and build my own. I usually see a pretty significant decrease in the culture penalty. Things like docks and whatnot appear to be able to stay w/out causing as much trouble.