Well, most obvious are:
- searching and extracting some rare loot from certain encounters.
- quests with time limit (just an option for certain quests).
- quests requiring you to pilot only certain ships (for the implementation part it can be done like this: player brings his own or receives stock quest ship, player can't access system where quest leads or start quest if his fleet has other ships).
- quests requiring certain combat actions(for example to use special EMP weapon in battle against enemy flagship).
- I don't know if its even possible(and its probably too much work), but quests where after accepting quest you immediately proceed into combat screen with your flagship, and the rest of the fleet being deployed and controled by AI, without ability to give tactical commands.
- quests where you collect/analyze/trade information. For example after battle with TriTachyon you may receive item/dialogue which states some information about possibility of attack on another faction. Or completing delivery quest as itself may be a valuable information someone will buy, like "I delivered something big to XXX station few days ago, wanna know more?" It probably may even affect diplomacy/what stations spawn or sell. Maybe even buying information about future diplomatic actions or what items someone will sell/buy for a good price. And it will be good, if there is an option to tell lies, which will destroy your connections with certain info traders, but may open path to others. But again it seems complex..
- quests with random encounters (when you are told to do something/explore and enemy fleet spawns and engages you suddenly).
- I don't know if its considered quest/included in your intentions, but general expansion of interaction between player and AI fleets. For example persuading fleet of Buffalo's to pay you for successfull protection. Or having a duel of flagships with enemy Admiral.
- classic quest of choices when quest giver lies about quest contents and reasons, and maybe rewards. And quest target depending on your choices may give you additional quest. Or it is possible that you take neither side and take it yourself what both sides are after (or prevent it?).
- finding certain fleet captains to try and deliver to them message from quest giver. Which may result in battle, additional quest, quest completion.
In general it would be fun if almost every option while questing will create different outcomes. For example taking both XXX0 and XXX1 items after battle will result in some accident, attack from giant fleet(item had hidden transmitter!!) etc. Or you will have 3 different items to give to quest giver. And every item will result in different outcome, but you will have to guess what is what with vague hints.