Whenever I'm playing against a quick little ******* character, I play defensively and wait for an opening.
Bowser can be pretty hard to uproot when you stay anchored to the stage, shield, fortress out of shield and shieldgrab a LOT.
Also, don't forget to leap at them and PoF (fire breath aimed down on them). I find that chasing quick characters only results in leaving openings for them to attack. Make them come to you and then punish them for their mistakes.
Specifically for Shiek, if she uses the dair, it opens her to a LOT of lag upon landing. If you can dodge it, you can either catch her in fire or at least get an easy grab in there and a fair always works, too.