While I really like the dramatic scene of Maul's entrance with the music, it is better to understand what he is doing first, then to have an unknown scene first.
Should Star Wars movies really be more about thinking whats going on or enjoying the ride?
I personally think Maul's significance is enough for TPM, you can improve Grevious's image in ROTS.
While I'd love to have a Maul = Grevious connection without new entire scenes (CGI wise) its a pointless quest since it leeds to more problems that it fixes.
There are ALOT more problems with the star wars universe than this, but thats just me.
Like Jar-Jar, little Ani, Watto, Boss Nass, Genoisis creatures (the leader makes clicking noises and the audience speeks in cheering (human chants)), Sifo-Dias, Dooku, Sidious, there are many more problems than this.