Workflows and by extension, custom workflow activities, execute totally asynchronously.
Plugins can execute both asynchronously and synchronously. Workflows can be manually executed, or automatically triggered by selected events.
Workflows can be limited to automatically execute within specific organizational scopes (ie. Org, BU, Parent and Child BUs, or for the Owner only).
Plugins are always triggered by the messages to which they’re subscribed, though some Messages allow limiting execution based on whether certain attributes have been passed into the Message.
Workflows can be turned off (by unpublishing). Plugins are always on. Custom workflow activities can be used in many Workflows.
Workflows can be developed through the Workflow design interface. Plugins must be developed in Visual Studio. Workflows do not require compiling (though custom workflow activities do). Plugins and custom workflow activities must be compiled and deployed through processes external to CRM.
In short: though only asynchronous in nature, Workflows allow an unimpeachable degree of flexibility and ease of configuration which Plugins do not afford, and their administration can be granted to power users of CRM without necessary access to the server or platform code. Plugins offer the highest degree of security and performance and surpass Workflows in capability and ability to augment platform operations.
When speed of execution, security of process, and validity of data are integral, I choose Plugins. When flexibility, functionality reuse, and optional user involvement are integral, I choose Workflows.