Good place to isntall a UBB with no ads it
www.f2s.com they support PHP MySQL and Perl.
Installing a UBB isn't that hard its mainly uploading and having to CHMOD files.
Adding message icons is easy you just have to add more icons with the next number in the sequence in the NonCGI icons folder. icon15.gif icon16.gif etc etc.
Instant Graemlins i don't know about, i imagine you could edit somewhere to change them.