Good questions:
1) They look important, i.e., sexy from a publishing standpoint. Whereas in reality, they're mostly just a hodge podge of data if not properly organized and clustered.
2) How you organize will be largely dependent on aesthetic outcome, especially if you end up trying to cluster rows and columns on the heatmap. You'll just have to try a few ways, and see which works best for you and the presentation of the data. Overall, people tend to prefer simpler heatmaps.
3) Best approach would be to do some sort of pathway or GO enrichment analysis first. I've been using GOexpress in R, which can be used directly to generate heatmaps. Also, it's unlikely that you have 13k DE genes. You will have to apply a filter. Most people use a hard cutoff of 2+ fold increase, or 50%- decrease. Though this is just a suggestion. For GO analysis, you may want to use a different filter, for example number or proportion of significantly enriched genes associated with a term ontology is a good place to start.
4) From my own experience, you want to normalize counts for heteroskedasticity across samples for each gene feature. However, I would first suggest doing some initial normalization of the raw counts, for example in DESeq theres library size correction, etc.
# use case for DESeq pipeline
exprs <- counts(cds,normalized=TRUE)
transpose_expr <- t(exprs)
scale_transpose <- scale(transpose_expr)
exprs <- t(scale_transpose)
5) I don't think anyone is really going to question it either way, but you can do additional validations. e.g., https://cran.r-project.org/web/packages/RankAggreg/vignettes/RankAggreg.pdf