A lazy init is a good init.
(IMO)
When to use with-eval-after-load
with-eval-after-load is loaded once when a certain feature or file is first loaded, so a keymap-change clearly goes inside one of these. Not the least because the keymap may not be known at init-time [try something like (define-key message-mode-map (kbd "C-c f") 'Footnote-add-footnote) in emacs -q]. A hook is not a nice solution here since it binds the function to a key every time the hook is started. As tarsius notes, you can read more about why not to local-set-key in hooks.
Finally, note that with-eval-after-load of GNU Emacs 24.4 is a 2 line wrapper around eval-after-load where body need not be quoted.
When to use hooks
Hooks are list of functions loaded every time a criterion is met, e.g. a certain mode is started. A common use of hooks is to load minor-modes, such as flyspell-mode or hl-line-mode. E.g. (add-hook 'org-agenda-mode-hook 'hl-line-mode). As Rémi points out, add-hooks is smart and will do the right thing even if the hook-variable has yet to been loaded. Nonetheless, I have many clauses like the following, which may be negligible for speed-gains, but does gives a sense of organization and dependency-structure:
(with-eval-after-load 'org-agenda
(add-hook 'org-agenda-mode-hook 'hl-line-mode))
Why add to hook after org-agenda? As always, C-h v org-agenda-mode-hook C-j delivers. The hook is defined in org-agenda.el as shown in *help*.
Loading extra features with-eval-after-load
with-eval-after-load is also important for loading extra features. You'd probably want something like (with-eval-after-load 'org (require 'org-inlinetask)) to load org inlinetasks. To see why (find-library "org-inlinetask"). Since org-inlinetasks.el directly (require 'org), all of the nice autoload that your friendly Emacs maintainers took great care to provide will be "ignored" and all of org.el(c) will be loaded.
But what if your (personal) defun is required several places? If you are really picky, you could put the defuns in another file in your load-path and add autoload cookies, or you can tell Emacs where to find the function with the autoload function. Then something like this would work:
(autoload 'org-cdlatex-mode "org" "cdlatex mode from org.")
(with-eval-after-load "latex"
(add-hook 'TeX-mode-hook 'org-cdlatex-mode))
Or you could just require org as it in turn would pull cdlatex
And, honestly, personal defun ain't gonna matter much for init time most of the time. The 1150 lines of personal defuns (84 defuns) in my init.el adds 0.02s over vanilla Emacs.
Measuring initialization time
An easy way to approximate intitialization time is
time emacs --eval "(kill-emacs)"
(benchmark against emacs -q.
But to get a more detailed approximation of where the initialization bottlenecks are check out Joe Schafer's esup.
Finally, loading time does not disappear magically. You are only pushing it forward (to the extend that you use all features in each session).