I am not happy with "of the book, of the sea".
Hello, Freeguy -- I am not happy with them, either.
Shouldn't they be: in the book, in the sea?
Yes, they should, at least from the standpoint of idiomaticity. "Of the book" is technically OK in (1), but there is the distracting sense that the problem may belong to the book.
You could, however, use the possessive and speak of "the book's most difficult problem." That would naturally be interpreted as referring to the most difficult problem in the book.
As for (2), you could use "of" and "in": "the most dangerous animal of all the animals in the sea." Incidentally, to avoid objections based on biological technicalities, you might change "animal(s)" to "creature(s)" or "life form(s)."