AE can render to PNG sequences (channels = RGB + Alpha.). Any other format has no use, c2 will convert it to PNG.
Meaning, for the little animations you are save. Dont forget the alpha channel.
Keep in mind that images are usually actually held in memory in a power-of-two size (e.g. 128x128, 256x256, 512x512, etc).
Best to respect that.
For the background. I suggest you try. Trying dont hurt.
Choose for a viewport that is not to big. Render in PNG sequence with NO alpha. It might help if you render at half the viewport and scale it in C2. You cant go for quality. Use a sprite, not a tiledbackground. Dissable colission for the sprite. Go for memory use and good load times. Try to do everything on 1 layer.
I think you can not parallax this background animation. It will be way to big to handle.
Its is not impossible, in my opion, for the background. But, yeah i can be wrong.
Its the way to go for the small animations.