Regarding flavor, I use any kind of good quality extract (jasmine, mint, vanilla, etc). You don't want to add too much water so you want to buy a brand that allows you to get the essence with just few dops.
For your coloring issue, I'm very surprise. I've been doing marshmallows for years now and never had any issue when using gel colouring. Are you sure it doesn't collapse when you don't use colouring (in other words, isn't your recipe that causes the issue ?) ?