This is an interesting question, but I think it is based on some false assumptions.
First, where does Bilbo say "Here is a sight I have never seen before."? I don't see it in LotR. (Frodo sees the sea in Galadriel's Mirror, and the narration says it was something he had never seen before.) As far as I can tell there's no evidence either way in LotR that Bilbo had traveled westwards from the Shire before.
Second, there is no evidence that Bilbo knew that there was a Palantir in the elf-towers west of the Shire. It looks like knowledge that the Palantir still existed was forgotten by all but lore-masters and some in Gondor, and even they had no idea where they were kept. (There were stories about the Seeing-stones of Numenor, but they were legends and bits of doggerel to most.)
Three Elf-towers of immemorial age were still to be seen on the Tower Hills beyond the western marches. They shone far off in the moonlight. The tallest was furthest away, standing alone upon a green mound. The Hobbits of the Westfarthing said that one could see the Sea from the lop of that tower; but no Hobbit had ever been known to climb it. Indeed, few Hobbits had ever seen or sailed upon the Sea, and fewer still had ever returned to report it. Most Hobbits regarded even rivers and small boats with deep misgivings, and not many of them could swim. And as the days of the Shire lengthened they spoke less and less with the Elves, and grew afraid of them, and distrustful of those that had dealings with them; and the Sea became a word of fear among them, and a token of death, and they turned their faces away from the hills in the west.
The Hobbits, at least, had no idea about the Palantirs. Their legends said that one could see the sea from the tops, but no Hobbit ever went to look.
Note that this makes it fairly likely that if Bilbo's wanderings took him outside the Shire, it may well have been westwards.
I want to see mountains again, Gandalf, mountains, and then find somewhere where I can rest.
So we can be sure he didn't travel far to the East. (Doubtless, if he travelled outside the Shire at all, he went to Bree, but no further east.) There was nothing in the North or to the south of the Shire -- both were barren -- while to the West were Dwarf mines (and he was friends with the Dwarves) and Elves still lived (likewise). Finally, the Great East Road (unlike the Greenway) was still in use both east and west of the Shire, and would be a natural director to travel.
We have reason to believe that Bilbo wandered -- or, at least, his Hobbit friends did:
Frodo went tramping all over the Shire with them; but more often he wandered by himself, and to the amazement of sensible folk he was sometimes seen far from home walking in the hills and woods under the starlight. Merry and Pippin suspected that he visited the Elves at times, as Bilbo had done.
(Note that the nearest Elven settlements were to the west in Ered Luin.)
Bottom line: It is plausible that Bilbo went west out of the Shire even as far as the Elven haven, but not definite.