Yeah CoH is an easy game once you've played about 1 or 2 games, played through campaign on hard not failing one mission, all quite easy, only thing that bothered me was population limit...
But them again it maybe easy for me because i've played rts games since i was like 6 or 7...
Medieval is a bit more challanging, i'm playing it on normall and doing fine, but its harder as coh...
It all depends on what you want:
As a starter i'd recommend CoH, if you'd be more used to rts i'd recommend medieval 2 instead...