The earliest ships of the United Earth Space Probe Agency were not strictly speaking exploration ships, though their fairly primitive technology made this their functional purpose. Barely able to achieve Warp 2 (and probably limited to significantly less - maybe even only enjoying subluminal but non-relativistic flight - early sources suggested that the Columbus class could not exceed 0.75 c), and with the Vulcans unwilling to share starmaps and other navigational data, early ships like the Columbus class often had to undertake extremely long voyages just understanding the layout of their immediate neighborhood. These initial voyages had to content more with natural threats than with artificial ones. When S.S. Icarus made first contact with the civilization on Alpha Centauri in 2085*, Earth had still not encountered the Kzinti for the first time.

In the years that followed, even though UESPA was forced to establish the Star Fleet to counteract intelligent threats and the Earth-Kzin Wars consumed significant resources that could otherwise have been used for space exploration, Earth continued to expand its frontiers. Newer, faster ships like the Cochrane class (in service 2097*-2117*) followed, and by the turn of the century Earth was dedicating significant resources into improving the warp speed and range of its exploration vessels. Initial progress was slow, in part because the Vulcans refused to transfer propulsion technology to Earth outside of very narrow categories, but S.S. Amity's successful Warp 2.7 flight demonstrated that Earth's indigenous research and development capabilities were up to the challenge of long-distance space exploration.

The trend towards rapidly iterating faster warp drives and longer-distance spacecraft culminated in the NX project, which achieved a series of rapid advances including the launch of NX-Delta, which reached Warp 3 in 2144, Franklin, which reached Warp 4  some time in the later 2140s, and finally NX-01 Enterprise, which reached Warp 5 in 2151. Over the strenuous objections of the Vulcans, these new ships allowed United Earth to not only contact many new civilizations, but also to establish cultural, trade, and scientific ties that were not as diligently committed to positive non-interference as the Vulcans. 

By the time the United Federation of Planets officially incorporated in 2161, United Earth had built a strong focus on exploration into the UESPA Star Fleet, and despite the ongoing Romulan threat, this influenced the new UFP Star Fleet to similarly maintain a focus. As the Star Fleet developed its chain of command, specialized commands formed to carry out the key missions of the Federation. While the Star Fleet maintained flexibility and inter-operability, Galaxy Exploration Command assumed primary responsibility for charting the enormous unexplored swaths of the Federation's territory. Initially conducted primarily using old ships such as the Horizon (2135*-2186*) and Freedom classes and their Andorian, Vulcan, and Tellarite equivalents, eventually the rugged and prolific Daedalus class came to be the main exploration ship of the UFP.

It was only as the Daedalus class was nearing the end of its maximum service life in the 2190s that Starfleet started seriously looking for a replacement to cover its exploration portfolio. The original plan was to entirely replace the Daedalus with the new Baton Rouge class multi-purpose cruisers, but ongoing delays on that design delayed its introduction until 2224*, neccessarily extending the Daedalus service period passed its planned 2196 retirement date. In 2204 the Daedalus received its final service life extension package, which included better warp propulsion and a number of other improvements (this is what Star Fleet Battles would call a WSR - Warp Refit Survey Cruiser) and continued to serve in that capacity for years yet to come.

The Daedalus class's replacements finally started to come on line in 2217 with the launch of the Einstein class (SFB equivalent: YCS Early Survey Cruiser), ahead of the long-delayed Baton Rouge. The Einsteins, along with more general purpose ships and eventually the small number of Baton Rouges not diverted to the once again fraught Kzinti border, carried out the Federation's exploration mandate until 2255, when U.S.S. Byrd entered service. 

To understand U.S.S. Byrd, it's important to understand the starships Pytheas, Archon, and Nordenskjold: the so-called Class 1 Light Cruisers. During the long road to making the Starship class program a reality, Robert April and his like-minded colleagues had to go through a number of rounds of proof-of-concept to demonstrate their assertions to the Federation Council. One such test involved refitting four older ships, U.S.S. Pytheas, U.S.S. Archon, U.S.S. Nordenskjold, and a second Baton Rouge class ship whose name remains unclear. The refitted ships were Einstein, Daedalus, and Baton Rouge, respectively, and in each case their refits included not only certain key systems for endurance testing, but also included interior renovation and refit for evaluating the efficiency of the proposed staffing and operational models for long-term exploration missions. These refits probably happened some time in the 2230s. 

Excerpted from J. Bob Rooney's colorized ship recognition chart

As an ensign, April had served aboard U.S.S. Gates, an Einstein class ships, and he was intimately aware of its operational characteristics. Much like the appearance of the Class 1 frigates which had not been part of the original design plan, it's not hard to imagine that April and the Federation Council both noted the potential value of a dedicated exploration ship built to meet the the Class 1 specifications and assigned to long distance missions. In fact, I think its not unreasonable to assume that this might have influenced the decision to largely demilitarize the heavy cruiser configuration of the Class 1 starship, as seen on the early laser-armed Constitution and Bonhomme Richard classes. 

However, history revealed that to fill their broad multi-purpose mission, the Class 1 cruisers required more capable defensive systems, and by the mid 2250s plans were in place to upgrade all the Constitutions and BHRs with top of the line phasers and more powerful shield systems which would necessarily cut into their flexibility for conducting scientific research. Moreover, it was expected that the Achernar configuration, already in planning, would roughly double the ship's crew complement, further reducing "free space" for scientific instruments, extra probe and shuttle inventory, and other consumables.

While it's unclear if the huge order for over 130 Achernar class ships had already come to pass, by this time it was almost surely taking form. One such ship being planned was NCC-1800, U.S.S. Tikopai. She was expected to launch in the late 2260s or early 2270s, but the Starfleet Corps of Engineers had already started preliminary design studies for the Achernar class to determine the initial fitting-out package and define broad objectives and thresholds for each subsequent batch of ships' capabilities within the large "superclass". 

Based on the concerns about degraded exploration capability after the phaser refit, NCC-1800 and a number of the planned Tikopai class ships were reprogrammed to a separate acquisition, now to be led by U.S.S. Byrd. While Byrd would also receive the phaser refit, her number of phaser emitters, photon torpedo launch tubes, and the size of her phaser capacitor were all reduced. Additionally, her shuttle bay was expanded to support a larger complement of small craft and her sensor array was dramatically improved to provide capabilities similar to the Hermes class scout. 

Artist's impression from starshipschematics.net. Note that initial GSCs probably had "Strange New Worlds" style warp nacelles given their commissioning date. 

Byrd commissioned in 2255, followed by ten more ships, including the replacement for U.S.S. Discovery (though records are fragmentary, this ship may have actually been commissioned as Einstein, with the Disco replacement ultimately built as a normal heavy cruiser under NCC-1798). When the Achernar class was authorized, these ships were retroactively returned to that acquisition, and they were scheduled for upgrades and ongoing sustainment as part of that effort. It was an open question at that time if the other 1800-series Achernars would receive the Byrd GSC package or if they would be standard heavy cruisers. 

Byrd went on to have a storied service life; around 2273 she was refitted with newer warp propulsion and additional probe launch capability. In 2277 she refitted again, this time with improvements to her shuttle bay to test the long-term operational use of tactical shuttles. She carried two Mk VIII tactical shuttles and the facilities to repair and reload them, and as the security situation became more tenuous in the 2280s she frequently diverted from her exploration duties to serve as a fast-response ship and perimeter action ship. We know she was still in service in 2286, but that is when the historical record goes silent on Byrd. 

That's quite a mystery, isn't it? A lot of sources influenced by Guenther & Sofia seem to agree that while the Achernar class never built its high numbered NCCs, there was a subsequent Tikopai class that was less capable than earlier Constitution refits but was suitable for mass construction and specifically intended for exploration missions. 

If we subscribe to multiverse theory, an easy exploration is that the Tikopai and Byrd classes are two different results of the same event: the cancellation of the high numbered Achernars. After all, let's face it - Star Fleet Battles is neccessarily in a parallel universe, since for legal reasons the prime universe can't and won't ever reflect its information in canon or licensed products (with a few rare exceptions like the Star Fleet Command computer games). 

However, I prefer to integrate sources whenever I can. So here's my theory. Guenther & Sofia indicate that 33 Tikopai class ships were built in total, including all the Byrd NCCs and a number more beyond that, up through NCC-1833. These ships were designed as relatively low cost deep space exploration ships with less in the way of tactical capabilities than the Connies. In a lot of ways, they sound like a modern take on the Sombra class. The first of these would have been U.S.S. Sardar, commissioning in 2278, so roughly around the same time that Byrd and her sister ships started to convert to light carriers. 

I hypothesize that what we call the Tikopai class is a Byrd class ship with the following modifications:

• Start with a GSC+; all of these ships would have the "plus" package at launch
• Delete the four Special Sensors boxes from the saucer
• Change the shields and all their characteristics to match a CA+
• Restore the two forward phasers to match the CA+
• Delete one Probe box
• Delete the option for operating and sustaining combat shuttles; cannot be converted to a CVL for wartime service

While the Tikopai class seemed destined for second-line duty, some of them got another lease on life. U.S.S. Powell (NCC unknown, but probably one of if not the last Tikopai launched) had an experimental configuration capable of very long-range operations. It included a new suite of advanced sensors even more advanced than the original Byrd class and could act as a tender for up to six large runabouts. After the success of this ship, U.S.S. Discovery/Einstein and then four Tikopais were converted to a similar configuration, albeit lacking the runabout-tender capabilities. These are the last iterations of the Byrd/Tikopai class that we know about, and its probable that they decomissioned around the same time the last of the Connies went out of service, around the 2320s.

In the time leading up to these ships exiting the fleet, they were replaced with the larger Constellation and Excelsior classes, and later yet by the Ambassador class. Eventually, the Federation's trend of building bigger and bigger explorers reached a peak with the Galaxy class, which as of the temporal divergence event of 2373 was the largest such ship we have reliable data on.