Quickly creating a sparse array

You can use the first documented usage for SparseArray:

So what you want to do is collect all of the rules {i,j}->val before passing them to SparseArray. There is already a built-in method for efficiently collecting a set of rules with no duplicate keys, namely AssociateTo.

So with a slight modification of the OP's code:

data=<||>;
Do[
   c = RandomInteger[{1, 10}];
   PossibleColumns = RandomSample[Range[i + 1, 10000], Min[10000 - i - 1, 30]];
   Do[
      AssociateTo[data, {PossibleColumns[[j]],i} -> c/RandomInteger[{1, 10}]];
      AssociateTo[data, {i,PossibleColumns[[j]]} -> c/RandomInteger[{1, 10}]];
      ,
   {j, 1, Length[PossibleColumns]}
   ],
{i, 1, 9999}
];

The above runs in ~3.5 seconds on my machine, and constructing the SparseArray is very fast as well:

SparseArray[Normal[data]] // AbsoluteTiming

Let's assume we are given the following data:

n = 100000;
k = 100;

g[i_] := RandomSample[i + 1 ;; n, Min[n - i - 1, k]];
f[i_, jlist_] := RandomReal[{1, 10}, Length[jlist]];

rowcolumnindices = g /@ Range[1, n - 1];
rowlengths = Length /@ rowcolumnindices;
rowvalues = MapIndexed[
   {jlist, i} \[Function] f[i[[1]], jlist], 
   rowcolumnindices
   ];

Probably the most efficient way to populate the sparse array with this data is by preparing the CRS data by hand and to use the following undocumented constructor:

First @ AbsoluteTiming[
 orderings = Ordering /@ rowcolumnindices;
 columnindices = Partition[Join @@ MapThread[Part, {rowcolumnindices, orderings}], 1];
 rowpointers = Accumulate[Join[{0}, Length /@ rowcolumnindices, {0}]];
 values = Join @@ MapThread[Part, {rowvalues, orderings}];
 M = # + Transpose[#] &[
   SparseArray @@ {Automatic, {n, n}, 0., {1, {rowpointers, columnindices}, values}}
   ];
 ]

1.53083

I used machine real values here (not rational numbers) because they will be processed much faster, in particular in Eigenvalues.

The CRS format assumes that the column indices for each row are in ascending order. This is why we have to sort the column indices and the corresponding values first (this explains the extra fuzz around orderings).