Custom Gateway Plugin

So, is it possible to automatically create an auto action when a plugin is installed? If yes, there needs to be a check to see if the auto actions plugin is installed, and if not, can it be packaged together (or automatically installed) with a new plugin?

You can do all of that in the install script of the plugin. Whether you load CB Auto Actions and use API or just do a direct database query to insert your activity is up to you.