There is no free lunch. Yes, with DBSCAN, you do not have to pick the number of clusters, but you must pick EPS and MinPts. Another choice that does not require picking the number of clusters is Mean Shift (either MeanShift or LPCM packages in R). But instead you have to pick the bandwidth parameter. The comments seem to focus on the size of your data, but I read your question as more about selecting a method and setting its parameters.
You started out mentioning K-means. There is lots of help about how to pick the number of clusters. Two good ones are the Wikipedia article on Determining the number of clusters in a data set and an earlier Cross Validated post on How to decide on the correct number of clusters
Another choice that (sort of) needs the number of clusters is hierarchical clustering. For this method, you don't need to choose the number of clusters up front. You build the hierarchy and then can explore it to see where to cut the tree. In the end, you still need to decide how many clusters, but you can get some idea of what that means as you do it. This method may not work so well
with a large number of points. It is $O(n^3)$, although you could sample your data to deal with this problem.
References: Wikipedia on Hierarchical Clustering
and Stack Overflow Documentation on
Hierarchical Clustering in R
As you noted, with DBSCAN, you do not need to choose the number of clusters, but you do need to choose EPS and MinPts. The choices of EPS and MinPts are not independent. They interact. I like to think of MinPts as depending on the problem and then there is a way to pick an appropriate
EPS. Whatever value you use for MinPts, any micro-cluster of size less than MinPts will be treated as noise. If you had a small but distinct cluster of 5 points, would you be willing to write it off as noise? You get stuck making the hard choice on MinPts, but once you make that choice, there is some help choosing EPS. At each point, DBSCAN will look at whether or not there are MinPts points within a radius of EPS. You can create the distance matrix for your data and look at the
distribution of distances to the $MinPts^{th}$ nearest neighbor. Often there will be good choices that make most points be core points and leave only the most extreme as noise. But DBSCAN has a downside. By picking MinPts and EPS, you are picking a single density for clusters that applies across your data. If you think that your data might have varying density between clusters, this may not work out for you.
DBSCAN References: Wikipedia on
DBSCAN and
DBSCAN Package in R
Another algorithm for which you do not specify the number of clusters is Mean Shift. You need to pick the bandwidth (the radius away from each point that will be used to estimate density). This does not tie you to a single density for all of the clusters, but you still need to decide the bandwidth -
essentially a statement of how far away you need to look to get a decent local density estimate.
Mean Shift References: Wikipedia on Mean Shift and
MeanShift package in R
In summary, you always have to specify something that will determine what is a cluster. It might be the number of clusters, some parameters that choose a density, or others, but you end up making choices. Since what you are trying to do is understand your data, I would recommend that you try several methods with various parameter settings and see if they help you converge on an understanding of your data set.