Horrible and Terrible are definetely more common in the UK as they are both originally from French, which is spoken just across the channel.

I'm in Canada and I think I hear "terrible" and "horrible" in the US as well as in Canada. You might be thinking of Americans saying other words that are synonymous with being vile or gruesome -- like "gross", which I'm not sure is more commonly said in Britain. And while I'm at it, for some reason, Americans use the word "disgusting" more than we do in Canada or in Britain. For example, let's say someone is using a sharp tone and is being impolite. Heard in England: "I don't like the way you speak to your mum. It's awful." Heard in Canada: "I don't like the way you speak to your mom. It's rude." Heard in America: "I don't like the way you speak to your mom. It's disgusting."

What do you think they would use as an alternative?

Yes, these words are common in the United States of America. Horrible is a word used for very bad descriptions. That storm caused terrible damage to the buildings in the city. The search for the missing child had a horrible ending when the child was found drowned.