You are correct, the histograms will be the same for each index as only the first column of the index is used. However remember that statistics also work out the densities for index columns and it calculates density for each combination of columns in a compound index eg for 1st column, 1st + 2nd, 1st + 2nd + 3rd, etc. Therefore although the 2 indexes will have the same histogram, they will have differing densities. The optimiser uses the densities to help it make more accurate estimates after evaluating the histogram, effectively refining it's estimates. Therefore although the first column is clearly required in the query before the index will even be considered, the additional column densities help the optimiser to choose which one to use, if any. As you rightly observe though, the columns in the "where" clause basically determine which index will be used.
The optimiser will choose a table scan if it estimates that using the index will in fact be more expensive. Consider a table with 500 data pages, all of which are read by a table scan. Compare to the case where using an index may perform a nested loop doing an index seek, but for many thousands of rows plus potentially a key lookup on the clustered index as well. It becomes far cheaper to just scan the 500 pages than jump about seeking thousands of individual rows. This is a obviously a very vague analogy, I'm just trying to highlight a potential scenario for you to show why a table scan may be used, even though an index exists.
As a general rule of thumb, make an index as selective as possible, putting the most unique columns first. Bear in mind the difference between a column having many distinct values and those values being unique. You mention 62 million rows but with column 1 having only 1000 distinct values. Any distinct value can obviously return many rows, possibly millions. Clearly it's an "it depends" situation, based on which columns are actually in each "where" clause though. However I would personally try adding an index with the date column first as it will most likely be used for those queries which contain the date, but which may currently be table scanning because of the value of the current first column not being unique enough in that particular instance, as the date will be more selective (unique) than your current column 1 is.
With indexing there is often no absolute right or wrong, and you will normally need multiple indexes to accommodate different queries, or are restricted in using a less efficient index simply because the where clause does not provide unique enough values. On a table with 62 million rows though, it's far better to have all the indexes necessary to support your full range of queries than risk a table scan.