If you're flying First, you can contact the You First service line 30 (or maybe 28...) days before departure and ask them to send you the menu. There is usually at least one vegetarian option on there. So you can check to see if that would suit you.
You say "seafood meal". That would put you more in the pescetarian category than the vegetarian category. In that case there you can look at the seafood meal in First as well, though you would have to check the menu to see if it also has animal products (example: scallops with bacon).
In Club, there is also usually a vegetarian option for the main meal, it is almost invariably pasta. There is also often a fish dish too. Starters are hit and miss, although one starter is often fish based, and there is always a cheese for dessert (the strict vegetarianism of the cheeses is variable). Vegetarianism in the second meal is hit and miss, mostly miss. If you choose to go with selections from the main menu, then bring your own food for the second meal. It is not possible to book only a second meal from the special meals section, it's all of the journey or nothing.
In both First and Club, you can pre-order your meal items leaving from Heathrow. This can help you to secure a vegetarian option.
Many people report that the vegetarian meal in First is the same as in Club. It is not the same as in World Traveller. I expect the Halal meals are also either "WT" or "Club", nothing different for First.