The best graphic plug-in is Glide64 Wonder Plus, i've never used any other. But go a head & try all the setting options one by one, it takes time but you want to do a re-texture, so you don't have much other choice.
Don't forget to post pics of your re-textures in the appropriate sub-forum High resolution textures projects, looking foreward to see them.