It sounds like both Seaside and Hinterlands would be good choices to start with.
I ended up getting Seaside. After playing a few campaigns and a few games against the computer, one of my first impressions is the noticeable increase in + action cards. The Base cards have +8 actions among the cards (2 for Village + Festival, and 1 for Lab, Market, Cellar, and Spy). In contrast, the Seaside cards have +16 actions among the cards (I am counting duration actions separately on each turn). This increases the chances that the Kingdoms will have good options for adding on a sequence of non-terminal cards to a enhance a terminal. For example, in the Base Game; Lab, Market, and Festival will all enhance a Militia terminal without building a more complex draw your deck type engine or trashing. Seaside adds far more cards that will enhance a Militia terminal without a draw your deck engine or trashing -- Treasury, Caravan, Bazaar, Lighthouse, Fishing Village, Warehouse, Haven, Peal Diver, Tactition (has duration action), etc. Kingdoms will generally have several decent enhancement options to choose from. This tremendously increases the number of useful combinations of cards that may be played in a game and ways different cards interact with each other.
The cards themselves also facilitate longer sequences of the same card than in base. For example, buying as many Lighthouses or Fishing Villages from Seaside as possible will generally be much closer to optimal than buying as many Moats or Villages as possible from Base. Or among terminals, buying as many Wharfs or Ghost Ships from Seaside as possible will be closer to optimal than buying as many Smithy/Council/Library or Militia from Base as possible. The increase in actions facilitates engines, but a different type of engine than base. The engines I go for in Base usually fall in two categories -- a sequence of Labs or an engine that may draw the full deck and often starts buying when reaching 2+ Provinces. The latter type of draw your deck and buy 2+ Provinces engine seems less common in Seaside. Wharf does this well, but outside of Wharf, I don't see a good source of drawing several cards for an engine, like with Smithy in Base. Sources of multiple buys also seem more limited with Treasury and Bazaar not having + buys, like Market and Festival. In Seaside, less precise engines seem to be more common, where it's more a sequence of +1 action / +1 draw cards than a draw your deck with careful balance of terminals and actions.
Earlier I mentioned liking Rush related strategies or more specifically strategies that lead to a different goal than the usual Provinces is highest priority, buy Dutchies/Gardens when 4/5/6 Provinces remain in deck, etc. As an example, I enjoy playing Bureaucrat + Market/Festival + Gardens types strategies, where the Bureaucrat works as a Gardens enabler, and the Market/Festival enhance it with their effects, often for buying copper. Islands don't appear to lead to this kind of unique Rush-like strategy to anywhere near the degree that Gardens does from Base. There also aren't as many good Gardens enablers in Seaside as there are in Base. Smugglers might be okay, if your opponent is buying something useful early on rather than trashing. Explorer could also be okay, but at +5 cost, it won't lead to as many useful strategies. I think the most likely candidate is Fishing Village. It would enhance the Bureaucrat / Gardens types strategy I mentioned earlier, although generally to a lesser degree than Market/Festival. I also expect the Fishing Village pile is going to be empty in a lot of games, leading to more 3-pile opportunities, but often in a less predictable way that depends on what your opponent does.
A good portion of the Seaside cards seem to be variations of Base cards. For example, Sea Hag and Ghost Ship have some obvious similarities with Witch and Militia, although the swapped prices and swapped +2 cards effects lead to very different strategies. I am particularly interested in the cards that do not have a good Base equivalent. I mentioned Treasure Map earlier. I do like playing Treasure Map even though I realize it is not the most useful card. There are times when it is useful, if there is a Warehouse, Haven, or Tactition is in the Kingdom and no strong attacks, although I realize this is not a common event. I can see some engine possibilities on uncommon occasions as well. My most enjoyable game against the computer involved a Warehouse + Treasure Map strategy. The Province pile was empty by turn 13.
I could continue discussing the expansion for pages, so it obviously has given me a lot to think about and opens the door to a tremendous number of new card combinations and new strategies, even though I have just played a few games at this point. I do like the expansion and think it can be a good choice as a 2nd expansion due to the relatively simple card effects, similarity with base game cards, and what I'd expect is getting better results than most expansions with bluntly almost always buying cards type strategies that are common among newer players. However, in retrospect, I think Hinterlands or maybe Adventures would have been a better fit for me than Seaside. It depends on the player. When it gets towards the end of the year, I plan to do a brief trial with all cards available, so I can get a better feel for which cards and expansions I enjoy most.
