Only one problem:
The ideal candidate to succeed Johnson -- having already coached both Dirk Nowitzki and Jason Kidd and reputed to have practiced a better blend of offense and defense in his various interim stints than his Hall of Fame-bound father -- is also the Mavericks' president of basketball operations.
And Donnie Nelson, according to club sources, does not want to leave his personnel post to return to an X's-and-O's life, convinced that the front office is where the Mavs need him more. Club sources also told ESPN.com that Cuban is well aware of that stance and will not try to force Nelson to reconsider.
So the Mavericks proceeded Wednesday with the first coaching hunt of the Cuban Era, with Nelson Jr. leading the search. Sources say Rick Carlisle will be the first interviewee, possibly as soon as Thursday, with Jeff Van Gundy also on the Mavs' list if Van Gundy shows interest in coaching next season.
Flip Saunders? Mike D'Antoni? Maybe even Eddie Jordan? Each of those guys, too, would likely be summoned for an interview if cut loose from their current teams.
D'Antoni, though, appears to be a long shot in Dallas for a few reasons:
(1) Suns president Steve Kerr told reporters in Phoenix that he'd "like to see" D'Antoni return next season, provided they can hash out what Kerr described as their well-chronicled "different ideas and different approaches" -- most of them related to defense -- at a meeting scheduled for Friday with owner Robert Sarver.
(2) NBA front-office sources say D'Antoni has a strong interest in the opening in Chicago -- which I'm told has a few Bulls players excited already -- if he and the Suns do agree to part company ... or D'Antoni simply resigns.
(3) Dallas would likely have some reservations hiring a coach known almost exclusively as an offensive specialist, similar to Johnson's predecessor, Don Nelson.
"We've got to bring a coach in that brings the best out of what he's got here," Nowitzki said Wednesday after the team's final meeting. "Open up the offense a lot more, run ... but still a guy that knows how to coach defense. Basically you don't want to go back to the Nellie days where we just run-and-gun and have fun and get scored on every time down."
It wasn't always that way back in the Nellie days. Donnie Nelson had the support of Nowitzki and former teammate Steve Nash whenever he filled in for his dad, largely because he struck more of a balance between offensive creativity and defensive detail than Nelson Senior. After engineering the 1998 trade that ultimately brought Nowitzki and Nash to Dallas -- believed to be the only deal in league history to net two future MVPs -- Donnie served as the Mavs' interim coach for 21 games in Cuban's first full season in 2000-01, posting a 13-8 record while Don Nelson recovered from prostate cancer surgery. Big Nellie originally planned to turn the reins over to the venerable Del Harris, but Harris told him that Donnie was a better fit at the time.
You can make a loud case that Donnie Nelson is the best fit at this time, too. The Mavs certainly need a creative offensive mind that can help Kidd in the half-court, and Nelson knows his strengths and weaknesses as well as anyone in the league, dating to his days as a Warriors assistant coach when Kidd was an Oakland high school legend and also having worked as an assistant in Phoenix during Kidd's time as a Sun.
Throw in Donnie's healthy respect for the defensive side of the ball, his longstanding relationship with Nowitzki and the most important factor -- he arguably remains Cuban's closest confidant in the organization despite the collapse of Cuban's relationship with Don Nelson -- and you inevitably wonder why the appointment hasn't already been made.
Here's the reason: Nelson gave up his coaching career to focus exclusively on the personnel side when Johnson replaced Don Nelson late in the 2004-05 season, believing he could do more for the franchise in that capacity ... and he doesn't want to go back.
Here's another: Cuban isn't contesting Nelson's inclination at least in part because there's clearly plenty of personnel work that needs to be done after two consecutive first-round flameouts, and given how slow and unathletic Dallas has looked in the last two postseasons after looking so much younger than mighty San Antonio in the 2006 playoffs.
Nowitzki turns 30 in June. Kidd turned 35 last month. Even if the midseason gamble on Kidd starts clicking next season with a coach who puts more motion into his half-court sets as opposed to reducing the new point guard to a guy who passes and runs to the corner, those two are going to need help. They need an all-new bench for starters (aside from Brandon Bass) as well as a big-time recovery from Josh Howard (unless they can find a trade taker) and a reliable shooting guard.
"I don't know if just a new coach can fix it all," Nowitzki said. "So I'm sure there will be some player movements. To me, the way we represented each other on the court, nobody should be safe. All of the players should be worried."
Cuban and Nelson weren't doing interviews Wednesday, but I'll go out on a limb and predict that Nowitzki is going nowhere this offseason. Ditto for Kidd, who'll be playing on a $21.4 million expiring contract in 2008-09. The Mavs' internal feeling remains that the trade (a) had to be made because Nowitzki had lost hope and because the previous iteration of the Mavs was going nowhere anyway, and (b) can't be judged fully until their new point guard is hooked up with a Kidd-friendly coach. So Nowitzki and Kidd will start next season as the Mavs' core twosome, with Kidd's contract theoretically offering the financial flexibility to launch a more drastic makeover at next February's trade deadline if things still aren't working.
Forecasting the outcome of the search for Johnson's successor, however, is considerably tougher. For all his perceived volatility, this is the first time Cuban has fired a coach. Don Nelson, remember, asked out more than he was pushed out in March 2005.
Remember this, too: Cuban inherited Nelson as a coach when he assumed control of the Mavs in January 2000, and ultimately gave him two contract extensions after hitting it off in those first few months together. Cuban targeted Johnson as Nelson's replacement when Avery was still a player, repeatedly observing Johnson's ability to lead and motivate from his daily seat in close proximity to the Dallas bench.
Yet giving this big job to someone he knows that well, as he likes to do in all of his businesses, doesn't seem possible for Cuban this time. Not unless Donnie Nelson -- who was, you might remember, once a hot-shot coaching prospect -- unexpectedly changes his mind and asks for his clipboard back.
After Johnson began to resist his guidance, Harris became an adviser with a direct pipeline to the owner and is referred to by Cuban as "my lifetime consultant." But neither Harris nor first-year Mavs assistant coach Paul Westphal is considered a candidate to take over for Johnson ... even though Cuban is said to be livid that Johnson refused to allow Westphal to provide the offensive input he was promised (or even to say much in huddles).
So unless he has a surprise planned -- which you must concede is always a possibility with Cuban -- all signs point to an appointment from outside the Mavs' comfort zone.
Not that things can get much more uncomfortable after the Mavs went to the brink of a championship in Johnson's first full season, lost that series with a historic collapse and never stopped the spiral ... none of which prevented Johnson from becoming increasingly stubborn along the way, even as his ability to reach his players and please his boss gradually deteriorated.
"It's called Successful Too Fast Disease," one team source said. "But the bottom line is that he lost the team."
Mavs swingman Jerry Stackhouse passionately rejected that theory, saying, "It would be a travesty and a fallacy to try to taint Avery's tenure here." But Nowitzki couldn't mask his frustration, albeit without specifying if the restrictive offense or the lack of focus from teammates like Howard peeved him most.
"I'm in my prime right now," Nowitzki said.
Which is why the Mavs' franchise player, coachless now for the first time in his career, sounded less worried about his next guy in and more dismayed that this feels "like it's another wasted year."
Marc Stein is the senior NBA writer for ESPN.com. To e-mail him, click here.