Something like this:

set_color_prompt() {
    _colorcombos() {
    PERL_HASH_SEED=109 perl -MB -e '
        use B;
        # color combinations that are readable (e.g. no red on red)
        @c =(map { "$_\n0\n" }
             6..7,9..11,13..15,40..51,75..87,113..123,147..159,171..231,249..254),
            (map { "$_\n231\n" }
             1..9,12..13,16..45,52..81,88..116,124..151,153,160..180,
             182..185,187..189,196..214,232..252,255..254);
        for(@ARGV) {
            print @c[hex(B::hash($_)) % $#c];
        }
        ' "$@"
    }
    local col=($(_colorcombos `whoami` `hostname` "`id`"))
    # (bg1,fg1)=user, (bg2,fg2)=host, (bg3,fg3)=path
    PS1='${debian_chroot:+($debian_chroot)}\[\033[48;5;'${col[0]}';38;5;'${col[1]}'m\]\u\[\033[00m\]\[\033[48;5;'${col[2]}';38;5;'${col[3]}'m\]@\h\[\033[00m\]:\[\033[48;5;'${col[4]}';38;5;'${col[5]}'m\]\w\[\033[00m\]\$ '
}

# set a fancy prompt (non-color, unless we know we "want" color)
case "$TERM" in
xterm-color)
    set_color_prompt
    ;;
xterm-256color)
    set_color_prompt
    ;;
*)
    PS1='${debian_chroot:+($debian_chroot)}\u@\h:\w\$ '
    ;;
esac

It will set a colored prompt based on whoami, hostname and id, so the color will also be different if you log in as a different user.

whoami, hostname and id are hashed, and based on the hash value a color combination is chosen. The combinations are tested to make sure they are readable.

Change PERL_HASH_SEED=109 to get different colors (e.g. if two important servers happen to give the same value).