That's a tough job. I'd start by pumping all brand promotion efforts away from Yahoo itself, into the various Yahoo Sites (finance, games, etc.) and away from search. Yahoo is so established in search, that it isn't necessary to promote that aspect of the company. Plus, it would be easier to establish that Yahoo is the leader in financial analysis and shopping results than trying to convince users that Yahoo can still hang with Google in search- it's an uphill battle not worth fighting.

After a bit of time passed, when it became visible what segments have potential, and what does not. It's time to cut. Surgically and decisively. The only way for Yahoo to compete in user-based web services is, in my opinion, to follow the Jack Welch method for cleaning up GE- cut everything that cannot make a reasonably stab at being the market leader. It saved GE from near certain doom. Under that same policy, GE has cut consumer electronics, their bread and butter for the first 50 years, but they are powerful and dominating in the spaces they do play in. Yahoo may have to ultimately drop search- it seems absurt to say it though. But as a company Yahoo has to trim the fat and cut the underperforming sectors. It's make or break time.

edit:Typos