We really don't need to keep a hash of letters, since the file is already sorted. We just need to keep track of what the last letter seen was:

#!/usr/local/bin/perl -w
use strict;

my $lastlet;
while (<DATA>) {
  print, next if /^\s*$/; # print and skip empty lines
  my $c = uc substr $_, 0, 1;      # get first character
  print ":$c:\n"
      if (!$lastlet || $lastlet ne $c);
  $lastlet = $c;
  print;
}

__DATA__
AA for apple
A for apple
BB for ball
B for ball
C for ....
[download]