In general, you want to use as few try blocks as possible, distinguishing failure conditions by the kinds of exceptions they throw. For instance, here's my refactoring of the code you posted:

try:
    server = smtplib.SMTP(host)
    server.login(username, password) # Only runs if the previous line didn't throw
    server.sendmail(addr, [to], msg.as_string())
    return True
except smtplib.socket.gaierror:
    pass # Couldn't contact the host
except SMTPAuthenticationError:
    pass # Login failed
except SomeSendMailError:
    pass # Couldn't send mail
finally:
    if server:
        server.quit()
return False

Here, we use the fact that smtplib.SMTP(), server.login(), and server.sendmail() all throw different exceptions to flatten the tree of try-catch blocks. In the finally block we test server explicitly to avoid invoking quit() on the nil object.

We could also use three sequential try-catch blocks, returning False in the exception conditions, if there are overlapping exception cases that need to be handled separately:

try:
    server = smtplib.SMTP(host)
except smtplib.socket.gaierror:
    return False # Couldn't contact the host

try:
    server.login(username, password)
except SMTPAuthenticationError:
    server.quit()
    return False # Login failed

try:
    server.sendmail(addr, [to], msg.as_string())
except SomeSendMailError:
    server.quit()
    return False # Couldn't send mail

return True

This isn't quite as nice, as you have to kill the server in more than one place, but now we can handle specific exception types different ways in different places without maintaining any extra state.