Single-cell RNA-seq (scRNA-seq) can in principle reveal the diversity of cell types or functional states within a heterogeneous tumor sample. However, major improvements are needed in sample processing and data analytics to achieve this goal. We have developed a suite of algorithms that are computationally inexpensive, make minimal statistical assumptions and comprehensively outperform existing approaches when benchmarked on scRNA-seq data. Based on these algorithms and a custom tissue dissociation protocol, we analyzed single-cell transcriptomes from >30 unsorted colorectal and lung primary tumors, with matched normal mucosa. The analysis yielded novel insights into tumor-specific stromal signatures, epithelial mesenchymal transition (EMT), cancer cell stemness and patient survival, and also revealed multiple cancer-associated fibroblast subtypes. Overall, our results indicate that hypothesis-free tumor-vs-control scRNA-seq of unsorted cell populations could be used as a general approach for investigating cancer mechanisms.