Very often the starting date for the databases we use online, or the original records that we view if we can go to the archives that hold them, come about because of a law mandating that the records should be kept. So if you get stuck, it can be useful to step back and ask what records were kept and which records survive. (See Determining what records are available in a particular locale?)
Outwards passenger lists from England are held at The National Archives in the record group BT 27 (Board of Trade records). These date from 1890-1960. BT 27 records are available to view online but that won't help you because the records don't start until after your 3-great-grandfather is already in New South Wales.
Your estimated window of arrival between 1860 and 1875 also may fall outside the range of findmypast's database New South Wales and Tasmania: Settlers and Convicts 1787-1859, but it's worth searching there anyway in case your estimate is a bit off. (As a general caution, some websites can be stricter than others about the date range they show you in the database titles -- at FamilySearch especially, read the description in the catalog and look for a note that tells you that some records fall outside the date range window.)
If you want to find information about your 3-great-grandfather's emigration, you'll have to find alternate sources for that information. Look for research guides like the guide to emigration on the TNA website, and for articles in genealogical publications that talk about emigration. TNA's guide says:
The website of The National Archives of Australia has more information
about emigration Australia. In addition, details of some 8.9 million
free settlers to New South Wales, 1826-1922 can be searched and
downloaded online at Ancestry.com.au, for a fee.
Their link takes you to a keyword search 'convicts' in the Ancestry Card Catalog. Be aware that the big box vendors like Ancestry sometimes bundle a big variety of records under one "umbrella" title that can be misleading. For a search for inbound records, it might be better for you to search wider by setting the location filter to Australia and to search the entire immigration and travel category and then to filter by location to get a list of possible databases to search.
Once you have the list of databases, click on the title to go to a dedicated search page for that collection (unless it is a browse-only collection). On Ancestry, read the About the Collection information to see what data sets have been included in that database. Going to the website of the archive where the original records are held, and searching for the catalog description there, will tell you more about the scope and content of the record set. Looking at the list of datasets, either from the About the Collection database, or by using the drop-down menu in the browse box on the right, gives clues about the nature of the records in that database.
You can also learn more about surviving records by looking for research guides on other websites like Genguide.co.uk -- see their guide to Emigration to Australia.
Another strategy is to read articles from academic journals, genealogical publications, and bloggers which discuss individuals who emigrated from Cornwall to Australia at the same time. When you find other reseachers' worked problems (case studies), read the articles carefully to see how the other researchers found information and how they put the information together as part of their profile or proof statement. Sometimes there is no direct evidence of their departure or arrival in a single source, and you have to put together information from several sources using indirect evidence in order to answer your question.
You've already narrowed down a window for his departure from Cornwall and have notes for his presence in New South Wales. But as you look for more information, it helps to construct a timeline for all the events you know about and the information you've gathered so far (for an example, see my question Finding residence information for Toronto in the 1840s?, which is about a similar case, only for Canada -- my subject family leaves England before the UK outbound passenger lists start in 1890, and arrives in Canada before the Canadian arrival lists start in 1895). Writing everything out in detail with bullet points (or making a spreadsheet) makes it easier to compare the events you know about and the events you want to find against the start/end dates of record collections. If you think of new research questions or other information you'd like to find as you create your timeline, write those things down on a separate checklist so you won't forget to follow up on those questions.
For tough questions like this, where you have to put together information with indirect evidence, I highly recommend making a research log before you start to search, and a genealogy source checklist so you can see at a glance what you've already found and what you want to look for. The FamilySearch Wiki and the Learning Center have good advice on setting up a research log:
