One correction: Catalan cuisine is Catalan cuisine, not "Spanish cuisine." Catalan cuisine has its own history, techniques, ingredients and identity, and is recognised as one of the great culinary traditions of the Mediterranean. If you're visiting Barcelona, I wouldn't look for "Spanish food", look for Catalan cuisine, because that's the local cuisine you'll actually be experiencing. That doesn't mean, of course, that you won't find restaurants serving other cuisines in a metropolitan city like Barcelona. You can also find a handful of specialised restaurants serving Castilian, Andalusian or Extremaduran cuisine, which many people would probably describe as "Spanish cuisine." But those are not the local cuisine.
Catalan cuisine
Catalan cuisine is much broader than seafood. The coast gets a lot of attention, but traditional Catalan cooking is just as much about meats, vegetables, mushrooms and slow-cooked dishes. If you enjoy pork, you're in luck. Look for botifarra amb mongetes (grilled Catalan sausage with creamy white beans), secret ibèric (a richly marbled cut of Iberian pork), galta de porc (slow-braised pork cheeks), or canelons a la catalana, traditionally filled with roast meats and topped with a silky béchamel. If you're after something a little more elaborate, try espatlla de xai al forn (slow-roasted lamb shoulder), fricandó (thin beef fillets gently braised with wild mushrooms), ànec amb peres (duck slow-cooked with pears, a classic sweet-and-savory Catalan combination), or cap i pota, one of the great traditional slow-cooked stews. In season, arròs de muntanya is another fantastic option: unlike seafood paella, it's a rich mountain-style rice made with pork, rabbit, mushrooms and sometimes sausages. And don't miss pa amb tomàquet, the deceptively simple tomato-rubbed bread that's an essential part of almost every Catalan meal.
That list does a better job of reflecting the breadth of Catalan cuisine. Visitors often associate it with seafood because of Barcelona's location, but historically Catalonia has always been a blend of sea and mountain ("mar i muntanya"), and many of its most iconic dishes come from the inland regions rather than the coast.
One dish you shouldn't overlook is fideuà, one of Barcelona's signature dishes. Often described as the city's answer to paella, it's made with short, thin noodles instead of rice, cooked in a wide, shallow pan until they develop a delicious toasted flavour while absorbing a rich stock. Although seafood fideuà is the best-known version, many restaurants also prepare excellent meat-based variations. If you enjoy Mediterranean comfort food, it's definitely worth trying while you're in Barcelona.
Where?
I should probably add a disclaimer: I rarely recommend restaurants because dining is such a personal experience. What feels romantic, good value or "the best meal" can vary enormously depending on people's tastes, expectations, mood and even the particular evening. So I'd take any recommendation, including mine, as a starting point rather than a guarantee. That said, based on what you've described, these would be among the places I'd look at first.
For a romantic anniversary dinner within your budget, I'd look at 1881 per Sagardi if having a harbour view is important. It has a lovely terrace overlooking Port Vell, serves plenty of excellent meat dishes alongside seafood, and fits your budget if you're not ordering wine. If you'd rather have a city rooftop atmosphere, La Terraza del Claris is another good option, with elegant surroundings, traditional Mediterranean cuisine, and a nice terrace.
