Having read both a long time ago, I also feel like Code Complete is the one to recommend: it covers more ground, is pragmatic, and more importantly most of its recommendations are based on studies, i.e. they come from empirical evidences. Clean Code compares poorly to this, in that it's just one guy's opinion.

That doesn't necessarily mean Clean Code is a bad book, but since our work relies primarily on logic, I'd rather have arguments presented to me logically.

Since both books cover pretty much the same ground, it makes more sense to recommend Code Complete.