There's essentially two options to replacing Moyes.
There is the Moyes part 2 approach where we pick a proisming young manager working in either the lower english leagues or the low quality foriegn ones and bring him here on a low wage and basically say "We're giving you a top club, make your name". Howe, Di Canio, Freedman, Poyet, Atkins, Zola etc. And of young english speaking anglophile managers yet to test themselves in a top league Solskjaer is probably the best even if the norwegian league is arguably of a worst standard then the championship.
If we're going that direction, he's the man I'd want.
Personally I'd rather we reinvested Moye's salary into an established european manager of the Emery, Cuper, Rehhagel type. The kind of manager who's done reliable jobs in the other big european leagues in managing the likes of valencia and bremen and roma and knows what it takes to compete with the big boys for champions league places and cups. But maybe that's shortsighted.