Seems to me that there is one thing Debian could do that would be very easy,
and bring it closer to "free" status (although still not fully there).
It should fork off non-free into a separate project, run by whoever likes it
in Debian now, and it should be hosted on seperate servers. Something like
debnonfree.org, and removed from Debian servers.
Essentially, this would not require any change to the debian system itself,
it would just require users of non-free to update their apt sources.list.
I think this would negate a large part of why it can't currently be
considered a fully free distro.
The other thing they need to do is to fix debian-installer (or d-i or
whatever it's called now) to make sure it doesn't recommend anything non-free
during the installation. That's a more major change for a later date.