I favor a hybrid approach.

Provide for color changes and styling within the plugin administration, storing the values in the database. Make this the default functionality. Then also provide the necessary CSS information so if a user wants to write his own CSS they can, and they can add this to their themes CSS.

If a user chooses to manage his own CSS he can tell the plugin not to output the database driven styles.

This approach satisfies the power users and developers as well as the novices who need a simple solution.

I'm not a big fan of the plugin itself having it's own static CSS file(s). Get to be too much to manage if a bunch of your plugins all have their own CSS files to juggle.